質問: x軸上にいくつかの線分があり、その線分の重なる数の最も大きい値を求める方法がわかりません。どのようなアルゴリズムで求めればいいのでしょうか? **例** ・線分1の範囲(2<=x<=5) ・線分2の範囲(3<=x<=9) ・線分3の範囲(4<=x<=11) の場合、 ![画像の説明をここに入力](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回重複 になります。
回答: 整数あつかいのみで良いなら、重複回数を記録する配列を用意すれば それほど手間をかけずにできそうです。 具体的なコードがないので疑似的コードでしめすと以下のようなイメージです。 いかがでしょう。 ``` 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; } } ```