62076


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回重複  
になります。


CC BY-SA 4.0
2020-01-08T06:02:13.767
62057
2020-01-09T01:48:43.253
2020-01-08T16:51:02.250
3060
34550
question
c アルゴリズム
C言語　直線状の線分の重複回数を求めるアルゴリズム


整数あつかいのみで良いなら、重複回数を記録する配列を用意すれば  
それほど手間をかけずにできそうです。  
具体的なコードがないので疑似的コードでしめすと以下のようなイメージです。  
いかがでしょう。

[code]

    void f_Foo()
    {
        int   重複回数サマリー[12];// 全て0に初期化する
    
        f_重複回数検査( 重複回数サマリー, 線分1);
        f_重複回数検査( 重複回数サマリー, 線分2);
        f_重複回数検査( 重複回数サマリー, 線分3);
        // 以上で各線分の重なり回数が、重複回数サマリー[n]にセットアップされたはず。
        // printするなりして確認しましょう。
    }
    
    void   f_重複回数検査(
       int *        サマリー配列,// (out)
       線分         対象線分)    // (in)
    {
        int i;
       for( i = 対象線分.開始位置 ; i<対象線分.終了位置 ; i++){//終了位置を含まない
          サマリー配列[ i] += 1;
       }
    }
    
[/code]


CC BY-SA 4.0
2020-01-08T07:01:45.503
62060
2020-01-08T07:10:07.110
2020-01-08T07:10:07.110
3793
3793
62057
answer


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

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

[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]


CC BY-SA 4.0
2020-01-08T15:30:54.393
62076
2020-01-09T01:48:43.253
2020-01-09T01:48:43.253
3605
3605
62057
answer


C 言語だときついな・・。

## 単純な方法

線の数：N  
開始点と終了を重複なく小さい順に並び替えます。(A)  
線分の開始点、終了点 が それぞれ どの位置にあるかを2次元配列を作成します。(X[2*N][2*N])  
i番目の線分の開始点と終了点の位置を x[i][bj] から x[i][ej] まで 1 で満たします。

この時のイメージ

[code]

    線１：　2 -- 5
    線２：　3 -- 9
    線３：　4 -- 11
    
    A[] 2, 3, 4 , 5, 9 , 11
    線１： 0 - 4  （開始点０、終了点４）
    線２： 1 - 5　
    線３： 2 - 6
    
    A[]      2, 3, 4 , 5, 9 , 11
    　　　　----------------------
             0  1  2  3  4  5  6
    　　　　----------------------
    x[0][] : 1, 1 , 1, 1, 1, 0, 0
    x[1][] : 0, 1 , 1, 1, 1, 1, 0
    x[2][] : 0, 0 , 1, 1, 1, 1, 1
    
[/code]

ここまでできれば、あとは x の 縦方向に 最大の個数を数えれば答えが出ます。

## より高度な方法

上記のアルゴリズムには一時作業領域が最大でも 4*N*N の領域が必要で  
Nが大量にある場合にメモリ不足になる可能性があります。

最大の 重複回数 **だけ** を求める事が要求されているのであれば  
線分を 開始純に並べたリストと、終了点順に並べたリストと  
すべての点を重複なく並び替えたリストを準備します。  
そして今の点で重なっている線を格納するリストを準備します。  
そして点の小さい順に、  
この点から 線が始まった時は、重なった線を入れるリストに追加  
この点で 線が終了した場合には 重なった線のリストから線を取り除く  
ループを作って このループの中の最大の リストの件数を答えとします。

こうすると利用するメモリは N の数倍程度で、並び替えを事前に行う事で  
終了点検索 検索のため O (N log N) 程度の時間で済むようになるはずです。

※ どこかの 競技プログラミングの 練習問題のようなきがしますが・・

## 追記

上記の方法では すべての線が重なるような場合に 処理時間と利用時間が増加します。  
線をリストに保持する事はしなくても 同じ答えが出せることに気づけば  
Hideki さんの回答が 最適な回答になると思います。

ただし、問題文の中にあいまいな仕様があるため、正しい答えは仕様によって  
違うと思います。  
線の開始と終了が一緒の場合があるか？  
線の 終了点と 別の線の開始点が 同じ点の場合に 重なっていると判断するか？

これによって 重なりの個数の計算方法は変わります。


CC BY-SA 4.0
2020-01-08T15:53:57.250
62077
2020-01-09T00:06:39.040
2020-01-09T00:06:39.040
18851
18851
62057
answer