LeetCode 瞑想: 重複しないインターバル

非重複間隔の説明は次のとおりです:

interval[i] = [start_i, end_i] の間隔の配列を指定すると、残りの間隔が重複しないようにするために削除する必要がある間隔の最小数を返します。

点でのみ接触する間隔は重なり合わないことに注意してください。たとえば、[1, 2] と [2, 3] は重複しません。

例:

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1

Explanation: [1, 3] can be removed and the rest of the intervals are non-overlapping.

または:

Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2

Explanation: You need to remove two [1, 2] to make the rest of the intervals non-overlapping.

または:

Input: intervals = [[1, 2], [2, 3]]
Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

---

この問題に対して、NeetCode は、前の問題で行ったように、間隔の並べ替えから始める優れた解決策を提供します。

変数を初期化して削除数を追跡することもできます。

intervals.sort((a, b) => a[0] - b[0]);

let numRemovals = 0;

間隔がソートされたので、各間隔を調べて、重複しているかどうかを確認します。そのために前の間隔の

end を追跡するので、最初の間隔の終了を最初に保持する prevEnd 変数を初期化しましょう:

let prevEnd = intervals[0][1];

メモ 2 つの間隔が

重なり合わない

Note

For two intervals not to overlap, the start of one should be strictly larger than the end of the other or the end of the one should be strictly smaller than the start of the other, as mentioned in our chapter introduction.

場合、一方の開始は終了よりも厳密に大きくする必要があります。 other または 1 つの 終わり は 厳密に指定する必要があります章の紹介で述べたように、他の の開始よりも小さい。

テーブル>

この問題では、間隔の終わりが他の間隔の開始と等しい場合、それらは重複していないとみなされます。

したがって、ここで、一方の開始が他方の終了よりも厳密に小さい場合、2 つの間隔は重複すると言えます。その場合、次の間隔と重複する可能性が低くなるように、prevEnd を 2 つの端の小さい方の値に更新します。それ以外の場合は、以前と同様に続行します:

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1

Explanation: [1, 3] can be removed and the rest of the intervals are non-overlapping.

最後に、numRemovals を返すことができます:

Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2

Explanation: You need to remove two [1, 2] to make the rest of the intervals non-overlapping.

そして、最終的な解決策は次のようになります:

Input: intervals = [[1, 2], [2, 3]]
Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

時間と空間の複雑さ

最初に間隔を並べ替えるので、時間計算量は になります。 $O(nlogn)$O(n log n) 。入力サイズが増加するにつれてサイズが増加する追加のデータ構造がないため、空間の複雑さは次のようになります。 $O(1)$O(1) .

---

次に、シリーズの最終章であるビット操作を開始します。それまで、コーディングを楽しんでください。

以上がLeetCode 瞑想: 重複しないインターバルの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。