Meditasi LeetCode: Selang Gabungan

Mari kita mulakan dengan penerangan untuk Selang Gabungan:

Memandangkan tatasusunan selang dengan selang[i] = [start_i, end_i], gabungkan semua selang bertindih dan kembalikan tatasusunan selang tidak bertindih yang meliputi semua selang dalam input.

Contohnya:

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].

Atau:

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

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

---

Kita boleh mulakan dengan mengisih selang dahulu, supaya kita boleh membandingkannya dengan mudah kemudian:

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

Selain itu, kita boleh memulakan tatasusunan hasil yang pada mulanya memegang elemen pertama selang yang baru diisih:

let result = [intervals[0]];

Kita perlu menjejaki tamat selang gabungan terakhir untuk membandingkannya dengan permulaan selang semasa yang sedang kita lihat untuk menyemak sama ada ia bertindih.

Nota Untuk dua selang tidak bertindih,

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.

permulaan satu hendaklah lebih besar daripada akhir yang lain atau hujung yang satu hendaklah lebih kecil daripada permulaan yang lain, seperti yang dinyatakan dalam pengenalan bab kami.

Jika ia tidak bertindih, kita hanya boleh menambah selang itu kepada hasil. Jika tidak, kita perlu mengemas kini "akhir akhir", dengan berkesan menggabungkan selang:

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].

Dan, satu-satunya perkara yang perlu dilakukan ialah mengembalikan hasilnya:

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

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

Dan, beginilah rupa penyelesaian akhir kami dalam TypeScript:

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

Kerumitan masa dan ruang

Kami sedang mengisih selang, dan fungsi isihan terbina dalam mempunyai $O(nlogn)$O(n log n) kerumitan masa. (Gelung ialah $O(n)$O(n) , tetapi kerumitan masa keseluruhan adalah $O(nlogn)$O(n log n) ).

Tatasusunan hasil boleh meningkat dalam saiz apabila saiz selang tatasusunan input meningkat, oleh itu kami mempunyai $O(n)$O(n) kerumitan ruang.

---

Seterusnya, kita akan lihat masalah terakhir dalam bab, Selang Tidak Bertindih. Sehingga itu, selamat mengekod.

Atas ialah kandungan terperinci Meditasi LeetCode: Selang Gabungan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!