Mengurutkan Interval Berdasarkan Awal
Mengurutkan acara sebelum memprosesnya
Mengurutkan Interval Berdasarkan Awal adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa Itu Interval
Interval hanyalah sepasang angka, yaitu awal dan akhir, seperti [2, 5]. Sebagian besar masalah interval berupa daftar pasangan seperti ini. 📏
Urutan Membuatnya Lebih Jelas
Interval mentah dapat datang dalam urutan apa pun, sehingga sulit dianalisis. Pengurutan terlebih dahulu mengubah kekacauan menjadi penelusuran rapi dari kiri ke kanan.
Urutkan Berdasarkan Awal
Langkah bawaan yang umum adalah mengurutkan berdasarkan nilai awal. Kini setiap interval dimulai pada atau setelah interval sebelumnya, sehingga Anda dapat melakukan satu kali penelusuran ke depan.
intervals.sort(key=lambda x: x[0])Tuple Terurut Secara Alami
Jika interval disimpan sebagai tuple, Python mengurutkannya berdasarkan elemen pertama, lalu elemen kedua, secara otomatis. Anda bahkan tidak memerlukan fungsi kunci di sini.
intervals = [(3, 7), (1, 4), (2, 5)]
intervals.sort()Mengapa Mengutamakan Awal
Mengurutkan berdasarkan awal memungkinkan Anda memproses peristiwa dalam urutan waktu. Interval berikutnya hanya dapat dimulai setelahnya, dan inilah invarian utama untuk penelusuran.
Kesamaan Nilai Awal
Ketika dua interval memiliki awal yang sama, kunci sekunder menentukan urutannya. Pengurutan berdasarkan (awal, akhir) menempatkan interval yang lebih pendek terlebih dahulu, yang sering kali membantu.
intervals.sort(key=lambda x: (x[0], x[1]))Terkadang Urutkan Berdasarkan Akhir
Beberapa masalah, seperti menjadwalkan sebanyak mungkin peristiwa, mengurutkan berdasarkan akhir. Pilih kunci yang sesuai dengan informasi yang diperlukan penelusuran Anda.
intervals.sort(key=lambda x: x[1])Biaya Pengurutan
Pengurutan membutuhkan waktu O(n log n), yang murah dan biasanya menjadi biaya terbesar dalam masalah-masalah ini. Penelusuran setelahnya hanya membutuhkan O(n).
Pertahankan Data Tambahan
Jika setiap interval membawa id atau bobot, urutkan seluruh catatan, bukan hanya batasnya. Kunci mengendalikan urutan, sementara datanya tetap ikut.
intervals.sort(key=lambda iv: iv[0]) # iv = (start, end, id)Urutkan Lalu Telusuri
Hampir setiap algoritma interval mengikuti pola sort terlebih dahulu, lalu telusuri. Dapatkan urutannya dengan benar, maka penggabungan, penghitungan, dan penjadwalan menjadi perulangan sederhana.
Model Mental Singkat
Bayangkan interval sebagai tamu yang datang ke sebuah pesta. Mengurutkannya berdasarkan awal akan menyusun waktu kedatangan mereka, sehingga Anda dapat menyambutnya satu per satu.
Pemeriksaan Cepat
Anda akan menggabungkan sebuah daftar interval.
Ringkasan
Interval adalah pasangan awal-akhir, dan pengurutan berdasarkan awal mengubah daftar yang berantakan menjadi penelusuran yang rapi. Urutkan terlebih dahulu, lalu proses ke depan dalam O(n). 🚀
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Mengurutkan Interval Berdasarkan Awal” gratis?
Ya — teks lengkap “Mengurutkan Interval Berdasarkan Awal” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Mengurutkan Interval Berdasarkan Awal”?
Mengurutkan acara sebelum memprosesnya Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Mengurutkan Interval Berdasarkan Awal” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Mengurutkan Interval Berdasarkan Awal
- Menggabungkan Interval yang Tumpang Tindih
- Line Sweep untuk Tumpang Tindih Maksimum
- Penghapusan Minimum agar Tidak Tumpang Tindih