O（n）よりもうまく解決できるかどうかを確認したいアルゴリズムの問題があります。
n 要素のテーブル T を指定しました。ここで、各要素はタプル (s_i、e_i) であり、N に s_i、e_i があり、s_i < e_i です。つまり、各タプルはある種の間隔です。N の t0、t1 および t0 < t1 で、特定の間隔 [t0、t1] と重なるすべての間隔を見つける必要があります。さらに、2 つのソートされたリスト S および E が利用可能で、それぞれ s 値または e 値と、T のそれぞれのエントリを指すインデックス i を含みます。リストはそれぞれ s 値または e 値でソートされます。(s と e の両方の値が一意であると仮定しましょう。)
問題：
s_i <= t1 および e_i >= t0 である T 内の各間隔/タプル (s_i、e_i) を見つける必要があります。
これまでの私の考え：
区間境界のいずれかを適用することで、いくつかの要素を除外できます。つまり、S で t1 を検索するか、E で t0 を検索します。これにより、残りの要素のリスト L が得られます。
L <- {e in E | e >= t0} or L <- {s in S | s <= t1}
ただし、どの検索を実行しても、L の要素数に下限はありません。さらに、前に実行した検索に応じて、それぞれ s <= t1 または e >= t0 の場合、L のすべての要素をチェックする必要があります。
このソリューションの複雑さは O(n) です。
ただし、k は区間 [t0, t1] と重なる要素の最大数であるとしましょう。k << n と仮定すると、L の適切な検索を選択することで少なくとも n/2 要素を除外できるため、複雑さは O(n/2) になります。それでも O(n/2) は O(n) の中にあります。
この問題を解決するためのより良いアプローチを考えられますか?
（この質問を自由に改善してください。あまり明確ではないかもしれません。ありがとう）