LeetCode 瞑想: マージ インターバル

マージ間隔の説明から始めましょう:

interval[i] = [start_i, end_i] の間隔の配列を指定すると、重複する間隔をすべてマージし、入力内のすべての間隔をカバーする重複しない間隔の配列を返します。

例:

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

Explanation: Since intervals [1, 3] and [2, 6] overlap, merge them into [1, 6].

または:

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]

Explanation: Intervals [1, 4] and [4, 5] are considered overlapping. 

---

後で簡単に比較できるように、最初に間隔を並べ替えることから始めることができます。

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

また、新しくソートされた間隔の最初の要素を最初に保持する結果配列を初期化することもできます。

let result = [intervals[0]];

最後にマージされた間隔の終了を追跡して、現在注目している間隔の開始と比較して、重複しているかどうかを確認する必要があります。

メモ 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.

開始は終了よりも厳密に大きくする必要があります。もう一方 または 一方の 終わり は、厳密に小さくする必要があります。章の紹介で述べたように、もう 1 つの の開始。 テーブル>

それらが重なっていない場合は、その間隔を結果に追加するだけです。それ以外の場合は、「最後の端」を更新して、間隔を効果的にマージする必要があります:

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

Explanation: Since intervals [1, 3] and [2, 6] overlap, merge them into [1, 6].

そして、最後にやるべきことは結果を返すことだけです:

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]

Explanation: Intervals [1, 4] and [4, 5] are considered overlapping. 

そして、TypeScript での最終的なソリューションは次のようになります。

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

時間と空間の複雑さ

間隔を並べ替えています。組み込みの並べ替え関数には があります。 $O(nlogn)$O(n log n) 時間の複雑さ。 (ループは $O(n)$O(n) ですが、全体的な時間計算量は次のようになります。 $O(nlogn)$O(n log n) ).

入力配列間隔のサイズが増加すると、結果配列のサイズも増加する可能性があるため、次のようになります。 $O(n)$O(n) 空間の複雑さ。

---

次に、この章の最後の問題、重複しない間隔について見ていきます。それまで、コーディングを楽しんでください。

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