次の問題を解決しようとしています: N 時間間隔が与えられ、それぞれが (開始、終了) として指定され、重複せず、開始に基づいて並べ替えられている - 特定の日付を含む間隔を見つけます。たとえば、次のようになります。
[1,4] [5,8] [9,10][11,20]
3 は最初のインターバルに、15 は 4 番目のインターバルに分類されます。
これまでのところ、次の基本的なアイデアがありました。
- バイナリ検索を使用して、対応する間隔 (Log N) を見つけることができます。
- いくつかの間隔だけが大きく、残りは小さい場合があるため、期間に基づいて間隔を並べ替える価値があるかもしれません。次に、統計的に、ほとんどの場合、最長の間隔 (O(1)) に「ヒット」しますが、これが N の最悪のケースの複雑さになる場合があります。
2つのアプローチを組み合わせる余地があるかどうかを考えていました。もう 1 つのアイデアは、期間に基づいて並べ替え、すべての間隔をツリーに挿入し、開始日で比較することです。これは、最悪の場合、最長の期間が時系列順に並んでいる場合、このアプローチのパフォーマンスは 2 に等しくなります。
私が想像した理想的な解決策は、一番上の最長の間隔を含むツリー (または同様のデータ構造) を持つことであり、2 つの分岐には次の 2 つの最長の間隔などがあります。ただし、分岐する方法がわかりませんつまり、長さに基づいて挿入するという明示的な仮定を行うため、ツリーの左側または右側を実際に破棄することはできません。
どんなコメントでも大歓迎です。