数直線の密集度について

Question

数直線があったとします。
タプル型で数直線の範囲を示すもの(a,b)が与えられれてるものとします(a<b)
これがn個与えられてるとして、一番密集している地帯の最大値(つまり、任意の範囲で、n個のうちx個がこの範囲が被っているうちの最大のx)
を求めたいのですが、これはどういう考え方をすればいいんでしょうか？
直感的にやっても正確な数字は求められないし、正確な数字を求めようと思ったら、nの中のm番目の範囲を取り上げたとして、m-1番目で既にT個範囲があったとして、これらを範囲ごとに個数を記録して、更にm個目の範囲で被りがある部分、ない部分を判定して更に細かく切り刻まなければいけない、と言う相当ややこしい場合分けになることが目に見えています。

nが1000になる事もあるので、こう言うことをしていたらタイムオーバーになる可能性も大いにあると思います。

ある程度目星をつけて大枠で絞り込むと言う方法も考えたのですが(例えば今わかっている最大の密集地帯の中から任意のdをとって、それを残ってる全ての範囲で確かめていく)などですが、とてもじゃないですがこのやり方では解けないはずです。

範囲の1点でも交わっていればその地点は交わっていると数えるので、例えば大枠の範囲を定めて、そこで数直線上の整数一個一個確かめて、と言うやり方もうまくいかないと思います。
解き方の見当が全くつかないです。
知恵をお貸しください
[追記]
一応自分が試したことの考え方のみを載せると、全く関わりを持たない独立した範囲の集合に分割はしました。
ただやっぱりその先でそれぞれの範囲ごとに切り刻んでいかなければいけないと思って、手が止まってしまっています。

Answer 1

a, bで表す区間が開区間(a, b)なのか閉区間[a, b]なのか半開区間(例えば[a, b))なのか、またa, bは実数なのか整数なのか質問にある文章では曖昧です。

本質的には大差ない話かも知れませんが実際にコードを書くにあたっては必要な条件となるのでもっと明快に問題を提示すべきと思います。

それはさておき、自分なら各区間の重複数(?)を積み上げグラフのようなものとしてイメージします。

この図は半開区間[1, 3), [3, 5), [4, 6)を仮定して区間の重なる数を関数と捉えてプロットしたものです。

こういうものを描く場合、区間[ai, bi)の開始・終了値ai, biを全て並べてソートし
[1, 3, 4, 5, 6]
のような数列を考え、各値のところで「区間が始まるなら+1して区間が終わるなら-1する」のように考え

[1,     3,     4,  5,  6] <-区間の開始終了値
[+1, -1 & +1, +1, -1, -1] <-区間数の増減
[1,     1,     2,  1,  0] <-区間数の増減を左から累加したもの

こういうデータを作ってやれば「区間の重なりの最大が2」であることは簡単に求まります。
実際にプログラミングする際には開区間なのか閉区間なのか半開区間なのかといったことに注意し、開始点、終了点の扱いを工夫する必要があるでしょう。そこはそこで考えようが色々あるかも知れませんがプログラミングテクニックとしてちょっと面白い感じなので考えてみるとよいと思います。自分なら開始点および終了点の値Xに対して
X-Δ
X
X+Δ
X+2Δ
(Δは論理の都合上無限小の値と考える)
のような4つの仮想的な点を考え「どこで+1してどこで-1するか、開始点なのか終了点なのかその値を含む区間なのか含まない区間なのかで調整」する方法を使います。

アルゴリズムとしての計算量は自分の案だと多分ソートに左右されるので例えばクイックソートならO(n log n)になると思います。

Comments

[babbleman]

回答有難うございます！
区間は小数、もっと言えば無理数です。また、開区間なので、端がわからない状態です。

[KSwordOfHaste]

そうでしたか。いずれにしても回答した考え方で少なくとも計算機の浮動小数点数の誤差が許す限りは期待どおりの結果が得られると思います。