C言語　直線状の線分の重複回数を求めるアルゴリズム


x軸上にいくつかの線分があり、その線分の重なる数の最も大きい値を求める方法がわかりません。どのようなアルゴリズムで求めればいいのでしょうか？

**例**  
・線分1の範囲(2<=x<=5)  
・線分2の範囲(3<=x<=9)  
・線分3の範囲(4<=x<=11)  
の場合、

[![画像の説明をここに入力](https://i.stack.imgur.com/DqXGY.png)](https://i.stack.imgur.com/DqXGY.png)

2<=x<=3, 9<=x<=11 の範囲で1回重複  
3<=x<=4, 5<=x<=9 の範囲で2回重複  
4<=x<=5 の範囲で3回重複  
になります。




数直線の左から右へ線分を探していったとき、線分の左の端が現れた時に重なりが増え、右の端が現れた時に重なりが減ることを利用します。

具体的には、線分の端点のデータを集めてソートし、順番に走査して、左端だったら重なりを一つ増やし、右端だったら一つ減らして、重なりを求めます。サンプルコードは

[code]

    #include <stdio.h>
    #include <stdbool.h>
    #include <stdlib.h>
    
    // 端点
    struct end_t {
        double x;
        bool isLeft;
    };
    
    // 端点の比較
    int compEnds(const void * p1, const void * p2) {
        const struct end_t * const pe1 = p1;
        const struct end_t * const pe2 = p2;
    
        if (pe1->x < pe2->x)
            return -1;
        if (pe1->x > pe2->x)
            return 1;
    
        // 線分の右端と別の線分の左端がおなじ座標の場合は
        // 線分は重なっていないものとする。
        if (pe1->isLeft && !pe2->isLeft)
            return 1;
        if (!pe1->isLeft && pe2->isLeft)
            return -1;
    
        return 0;
    }
    
    // 線分
    struct segment_t {
        double left;
        double right;
    };
    
    // 線分のデータ
    #define NUM_SEGMENTS (3)
    struct segment_t Segments[NUM_SEGMENTS] = {
        { 2.0, 5.0 },
        { 3.0, 9.0 },
        { 4.0, 11.0 },
    };
    
    int main() {
        // 端点データのセットアップ
        struct end_t ends[NUM_SEGMENTS * 2];
        for (int i = 0; i < NUM_SEGMENTS; ++i) {
            ends[2 * i].x = Segments[i].left;
            ends[2 * i].isLeft = true;
            ends[2 * i + 1].x = Segments[i].right;
            ends[2 * i + 1].isLeft = false;
        }
    
        // 端点データのソート
        qsort(ends, NUM_SEGMENTS * 2, sizeof(struct end_t), compEnds);
    
        //　重なりを求める
        int maxOverlaps = 0;
        int currentOverlaps = 0;
        for (int i = 0; i < NUM_SEGMENTS * 2; ++i) {
            if (ends[i].isLeft) {
                ++currentOverlaps;
                if (currentOverlaps > maxOverlaps)
                    maxOverlaps = currentOverlaps;
            }
            else {
                --currentOverlaps;
            }
        }
    
        printf("Max overlaps: %d\n", maxOverlaps);
    
        return 0;
    }
    
[/code]




数直線の左から右へ線分を探していったとき、線分の左の端が現れた時に重なりが増え、右の端が現れた時に重なりが減ることを利用します。

具体的には、線分の端点のデータを集めてソートし、順番に走査して、左端だったら重なりを一つ増やし、右端だったら一つ減らして、重なりを求めます。サンプルコードは

[code]

    #include <stdio.h>
    #include <stdbool.h>
    #include <stdlib.h>
    
    // 端点
    struct end_t {
        double x;
        bool isLeft;
    };
    
    // 端点の比較
    int compEnds(const void * p1, const void * p2) {
        const struct end_t * const pe1 = p1;
        const struct end_t * const pe2 = p2;
    
        if (pe1->x < pe2->x)
            return -1;
        if (pe1->x > pe2->x)
            return 1;
    
        // 線分の右端と別の線分の左端がおなじ座標の場合は
        // 線分は重なっていないものとする。
        if (pe1->isLeft && !pe2->isLeft)
            return 1;
        if (!pe1->isLeft && pe2->isLeft)
            return -1;
    
        return 0;
    }
    
    // 線分
    struct segment_t {
        double left;
        double right;
    };
    
    // 線分のデータ
    #define NUM_SEGMENTS (3)
    struct segment_t Segments[NUM_SEGMENTS] = {
        { 2.0, 5.0 },
        { 3.0, 9.0 },
        { 4.0, 11.0 },
    };
    
    int main() {
        // 端点データのセットアップ
        struct end_t ends[NUM_SEGMENTS * 2];
        for (int i = 0; i < NUM_SEGMENTS; ++i) {
            ends[2 * i].x = Segments[i].left;
            ends[2 * i].isLeft = true;
            ends[2 * i + 1].x = Segments[i].right;
            ends[2 * i + 1].isLeft = false;
        }
    
        // 端点データのソート
        qsort(ends, NUM_SEGMENTS * 2, sizeof(struct end_t), compEnds);
    
        //　重なりを求める
        int maxOverlaps = 0;
        int currentOverlaps = 0;
        for (int i = 0; i < NUM_SEGMENTS * 2; ++i) {
            if (ends[i].isLeft) {
                ++currentOverlaps;
                if (currentOverlaps > maxOverlaps)
                    maxOverlaps = currentOverlaps;
            }
            else {
                --currentOverlaps;
            }
        }
    
        printf("Max overlaps: %d\n", maxOverlaps);
    
        return 0;
    }
    
[/code]

