Meditasi LeetCode: Selang Tidak Bertindih

Penerangan untuk Selang Tidak Bertindih ialah:

Memandangkan tatasusunan selang selang di mana selang[i] = [start_i, end_i], kembalikan bilangan minimum selang yang perlu anda alih keluar untuk menjadikan selang selebihnya tidak bertindih.

Perhatikan bahawa selang yang hanya menyentuh pada satu titik adalah tidak bertindih. Contohnya, [1, 2] dan [2, 3] tidak bertindih.

Contohnya:

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.

Atau:

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.

Atau:

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.

---

Untuk masalah ini, NeetCode mempunyai penyelesaian hebat yang bermula dengan mengisih selang, seperti yang kami lakukan dalam masalah sebelumnya.
Kami juga boleh memulakan pembolehubah untuk menjejaki bilangan pengalihan keluar.

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

let numRemovals = 0;

Sekarang selang kita diisih, kita akan meneliti setiap satu, menyemak sama ada ia bertindih atau tidak. Kami akan menjejaki tamat selang sebelumnya untuk itu, jadi mari kita mulakan pembolehubah prevEnd yang pada mulanya memegang hujung selang pertama:

let prevEnd = intervals[0][1];

Nota Untuk dua selang

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.

tidak bertindih, mula satu harus lebih besar daripada akhir yang lain atau hujung satu harus ketat lebih kecil daripada permulaan yang lain, seperti yang dinyatakan dalam pengenalan bab kami. table>

Dalam masalah ini, apabila penghujung selang adalah sama dengan permulaan yang lain, ia dianggap tidak bertindih.

Jadi, di sini kita boleh mengatakan bahawa dua selang akan bertindih jika permulaan satu adalah kurang daripada penghujung yang lain. Dalam kes itu, kami akan mengemas kini prevEnd menjadi nilai yang lebih rendah daripada kedua-dua hujung supaya kami mempunyai peluang yang kurang untuk bertindih dengan selang seterusnya. Jika tidak, kami akan meneruskan seperti sebelumnya:

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.

Akhir sekali, kami boleh mengembalikan 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.

Dan, penyelesaian akhir yang kami ada kelihatan seperti ini:

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.

Kerumitan masa dan ruang

Memandangkan kita mengisih selang pada permulaan, kerumitan masa ialah $O(nlogn)$O(n log n) . Kami tidak mempunyai struktur data tambahan yang saiznya akan meningkat apabila saiz input meningkat, jadi kerumitan ruang adalah $O(1)$O(1) .

---

Seterusnya, kita akan memulakan bab terakhir siri ini, Manipulasi Bit. Sehingga itu, selamat mengekod.

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