3

[start,end] の形式の N 個の間隔があるとします。範囲全体がこれらの間隔でカバーされているかどうかを確認する必要があります。

例: 間隔が [4.5,5.765] および [5.8,10] で、間隔が [5,10] の場合、同じデータについて間隔が [6,9.99] の場合、true と報告する必要があります。

1e-9 の精度が必要です。間隔と範囲は [-1000,1000] になります。

この問題は O(NlgN) 時間で解決できますか?? ここで、N=間隔の数です。

4

3 に答える 3

2

すべての間隔（O(N * log N)）の開始点と終了点を並べ替えると、O(N)パスで次のことを追跡できます。

  • -1000との間の数直線上の現在の位置1000。これは、任意の間隔の各開始点/終了点を取ります。
  • 「現在」開いている間隔の数、つまり、数直線上のこの点で交差する間隔の数。

このパスのいずれかの時点で、現在の値がターゲット範囲内にあり、現在の間隔の数が0の場合、ターゲット範囲は間隔の対象外です。ターゲット範囲の終わりに到達する前にそれが決して起こらない場合、ターゲットはカバーされます。

間隔は閉じているので、値のある「始点」のr 前に値のある「終点」をソートすることを忘れないでください。間隔がとでターゲットがrの場合は必ず「true」を返します。[0,1][1,2][0,2]

+/- 1000の範囲の粒度には、IEEE倍精度で十分ですが、2進浮動小数点で正確に表現できない1e-9問題に注意してください。5.8したがって、間隔の計算方法によっては、計算エラーまたは表現エラーによって小さな「ギャップ」が生じる可能性があります。このため、開始する前に、10億分の1に四捨五入したり、関連する値の基数2ではなく基数10の表現を使用したりすることをお勧めします。

于 2012-09-09T22:45:17.960 に答える
1

あなたはすでにいくつかの良い答えを得ていますが、私は単純明快なものに貢献したいと思いました。

間隔がオーバーラップできるかどうかを教えてくれなかったので、オーバーラップできると仮定します。(それ以外の場合は、単純な O(N) 検索パスで、範囲がいずれかの間隔内にあるかどうかがわかります。)

間隔のセットが複数の範囲で一定のままである場合、最善の策は、開始点に従って間隔を事前に並べ替えることです。(これは通常 O(N logN) 操作ですが、一度だけ実行する必要があります)。次に、次のことができます。

checkRange(range, intervals[])
    for each ( intv in intervals )
        if intv.start > range.start
            return false
        if intv.end >= range.end
            return true
        if intv.end > range.start
            range.start = interval.end

    return false

これはたった 1 つの O(N) パスです。

間隔のセットが範囲ごとに変化する可能性がある場合、次の再帰アルゴリズムは、毎回間隔をソートするよりもパフォーマンスが良い場合とそうでない場合があります。

delta = 1e-9

checkRange(range, intervals[])
    for each ( intv in intervals )
        if intv.start <= range.start and intv.end >= range.end
            return true
        if intv.end < range.start or intv.start > range.end
            continue
        if intv.start < range.start and intv.end > range.start
            range.start = interval.end
            continue
        if intv.start < range.end and intv.end > range.end
            range.start = interval.end
            continue
        range1 = new range(start = range.start, end = intv.start - delta)
        range2 = new range(start = intv.end + delta, end = range.end)
        intervals = intervals after intv
        return checkRange(range1, intervals) and checkRange(range2, intervals)

配列またはリンクされたリストの場合intervals after intv、元の と同じメモリ空間に保持できるためintervals[]、これは再帰反復にスタック空間を使用するだけで、それ以上は使用しません。計算の複雑さについては、私よりも優れた誰かがそれについて証明することを検討する必要がありますが、おそらくかなりまともだと感じています.

于 2012-09-10T00:03:02.773 に答える
0

あいまいソートを実行できます。 最良のケースはO(n)平均的なケースO(n log n)です。これはクイックソートに似ています。最良のケースは、すべての区間に少なくとも 1 つのポイントが存在する場合、つまりすべての区間が重なっている場合に発生します。一般に、オーバーラップが多いほど、アルゴリズムは他のソート アルゴリズムよりも優れています。

以下は、このアルゴリズムの詳細な分析です。http://web.media.mit.edu/~dlanman/courses/cs157/HW3.pdf

于 2012-09-10T12:28:21.240 に答える