0

OK、これは上級アルゴリズム クラスで受けた質問です。私はすでに解決策を一度提出しましたが、効率の問題でインストラクターに拒否されました。つまり、私はすでに自分の側で努力したのに、彼のヒントにもかかわらずそれを得ることができなかったので、優しくしてください. 以下に彼のヒントを示します

開始点と終了点の両方を持つ間隔の配列が与えられた場合、各間隔について、その中に含まれる他の間隔の数を見つけます。間隔の数が 10^9 未満で、それらの ID が異なります。start と end が 10^18 未満の場合、入力ファイルに start と end の重複する番号が含まれていません。上記の数字はすべて整数です

ヒントは、バケットを使用したデータ構造を検討することです。アルゴリズムは O(n^2) よりも高速である必要があります

sample input and output

input:
5   %% number of intervals
2 100 200    %% id, start,end. all lines below follows this
3 110 190
4 105 145
1 90 150
5 102 198

output:
3 0
4 0
1 1
5 2
2 3
4

1 に答える 1

1

数値はかなり大きいので、O(N log N) は多すぎるかもしれませんが、ここにアイデアがあります。

まず最初に値を正規化します。つまり、同じ順序を維持しながら値を小さくします。あなたの例では、正規化は次のようになります

 90 100 102 105 110 145 150 190 198 200
  1   2   3   4   5   6   7   8   9  10

したがって、新しい間隔は次のとおりです。

5
2 2 10
3 5 8
4 4 6
1 1 7
5 3 9

これで、区間のエッジは [1, 2N] の範囲内になりました。

間隔を最後で並べ替えます。

5
4 4 6
1 1 7
3 5 8
5 3 9
2 2 10

間隔に達すると、その間隔より前に開始され、まだ遭遇していないすべての間隔の答えが 1 増加する必要があると言えます。これは、SegmentTree を使用して実行できます。

間隔 [x, y] を取得したときに行うことは、範囲 [1, x - 1] 内のすべての値を 1 増やしてから、セグメント ツリーの x の値としてその答えを計算します。これは、間隔の加算とポイントのクエリにすぎません。これは、一般的なセグメント ツリーの問題です。

この問題を O(N log N) 未満の時間と O(N) メモリで解決できるとは思えないため、このソリューションは時間と空間の両方で漸近的に最適なソリューションになるはずです。

于 2013-08-21T22:21:17.590 に答える