algorithm - 処理間隔

Question

指定された範囲内にある間隔の数を見つける方法。たとえば、範囲[1,10]があり、提供された間隔が(1,3)、(1,8)、(2,4)、(2,5)、(2,3)であると仮定して、質問を説明しましょう。 ,(3,9),(3,8),(3,6) そして、範囲 [1,5] の間に入る間隔の数を調べるように依頼すると、答えは 4 です。これらは 4 つの [(1 ,3),(2,4),(2,5),(2,3)] の間隔は [1,5] の範囲にあります。Range[1,N] があり、間隔を提供するのと同じように、指定された範囲内にいくつの間隔があるかを調べる方法.すべてのクエリでこのタスクに最適な複雑さは何ですか?

Answer 1

の上）。これ以上のことはできません。少なくとも、すべての間隔がクエリに対して有効であることに答える必要があります。これは O(n) です。query_min <= interval_min && query_max <= interval_max かどうかをテストするためにリストを反復処理するだけで、O(n) を取得できます。