x軸上にいくつかの線分があり、その線分の重なる数の最も大きい値を求める方法がわかりません。どのようなアルゴリズムで求めればいいのでしょうか?
例
・線分1の範囲(2<=x<=5)
・線分2の範囲(3<=x<=9)
・線分3の範囲(4<=x<=11)
の場合、
2<=x<=3, 9<=x<=11 の範囲で1回重複
3<=x<=4, 5<=x<=9 の範囲で2回重複
4<=x<=5 の範囲で3回重複
になります。
数直線の左から右へ線分を探していったとき、線分の左の端が現れた時に重なりが増え、右の端が現れた時に重なりが減ることを利用します。
具体的には、線分の端点のデータを集めてソートし、順番に走査して、左端だったら重なりを一つ増やし、右端だったら一つ減らして、重なりを求めます。サンプルコードは
#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;
}
C 言語だときついな・・。
線の数:N
開始点と終了を重複なく小さい順に並び替えます。(A)
線分の開始点、終了点 が それぞれ どの位置にあるかを2次元配列を作成します。(X[2*N][2*N])
i番目の線分の開始点と終了点の位置を x[i][bj] から x[i][ej] まで 1 で満たします。
この時のイメージ
線1: 2 -- 5
線2: 3 -- 9
線3: 4 -- 11
A[] 2, 3, 4 , 5, 9 , 11
線1: 0 - 4 (開始点0、終了点4)
線2: 1 - 5
線3: 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
ここまでできれば、あとは x の 縦方向に 最大の個数を数えれば答えが出ます。
上記のアルゴリズムには一時作業領域が最大でも 4*N*N の領域が必要で
Nが大量にある場合にメモリ不足になる可能性があります。
最大の 重複回数だけを求める事が要求されているのであれば
線分を 開始純に並べたリストと、終了点順に並べたリストと
すべての点を重複なく並び替えたリストを準備します。
そして今の点で重なっている線を格納するリストを準備します。
そして点の小さい順に、
この点から 線が始まった時は、重なった線を入れるリストに追加
この点で 線が終了した場合には 重なった線のリストから線を取り除く
ループを作って このループの中の最大の リストの件数を答えとします。
こうすると利用するメモリは N の数倍程度で、並び替えを事前に行う事で
終了点検索 検索のため O (N log N) 程度の時間で済むようになるはずです。
※ どこかの 競技プログラミングの 練習問題のようなきがしますが・・
上記の方法では すべての線が重なるような場合に 処理時間と利用時間が増加します。
線をリストに保持する事はしなくても 同じ答えが出せることに気づけば
Hideki さんの回答が 最適な回答になると思います。
ただし、問題文の中にあいまいな仕様があるため、正しい答えは仕様によって
違うと思います。
線の開始と終了が一緒の場合があるか?
線の 終了点と 別の線の開始点が 同じ点の場合に 重なっていると判断するか?
これによって 重なりの個数の計算方法は変わります。
整数あつかいのみで良いなら、重複回数を記録する配列を用意すれば
それほど手間をかけずにできそうです。
具体的なコードがないので疑似的コードでしめすと以下のようなイメージです。
いかがでしょう。
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;
}
}