0Pricing
Competitive Programming Academy · Pelajaran

Penghapusan Minimum agar Tidak Tumpang Tindih

Penjadwalan greedy dengan mempertahankan interval yang selesai paling awal

Penghapusan Minimum agar Tidak Tumpang Tindih adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 4 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 Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.

Tujuan Penghapusan

Anda memiliki interval yang saling tumpang tindih dan ingin melakukan sesedikit mungkin penghapusan agar tidak ada lagi yang tumpang tindih. Pertahankan sebanyak mungkin. ✂️

Balik Masalah

Melakukan penghapusan sesedikit mungkin sama dengan mempertahankan sebanyak mungkin interval yang tidak tumpang tindih. Selesaikan versi mempertahankan, lalu jumlah penghapusan adalah n dikurangi jumlah yang dipertahankan.

Ini adalah Pemilihan Aktivitas

Mempertahankan sebanyak mungkin interval yang tidak tumpang tindih sebenarnya adalah masalah klasik pemilihan aktivitas. Gagasan rakus yang sama menyelesaikan keduanya.

Urutkan berdasarkan Waktu Berakhir

Di sini, urutan yang tepat adalah berdasarkan waktu berakhir, bukan waktu mulai. Selesai lebih awal akan secepatnya membebaskan linimasa untuk interval berikutnya yang mungkin Anda pertahankan.

intervals.sort(key=lambda x: x[1])

Pilihan Rakus

Selalu pertahankan interval yang berakhir paling awal di antara interval yang masih kompatibel. Dengan begitu, ruang yang tersisa untuk interval lain menjadi maksimal.

Lacak Waktu Berakhir Terakhir yang Dipertahankan

Simpan waktu berakhir interval terakhir yang Anda pertahankan. Interval berikutnya kompatibel hanya jika waktu mulainya berada pada atau setelah batas tersebut.

if start >= last_end:
    last_end = end

Hitung Penghapusan

Saat sebuah interval dimulai sebelum last_end, interval itu berkonflik, jadi Anda buang dan menambahkan satu pada jumlah penghapusan. Jika tidak, Anda mempertahankannya.

else:
    removed += 1

Mengapa Waktu Berakhir Paling Awal Menang

Argumen pertukaran membuktikannya: mengganti interval yang dipertahankan dengan interval kompatibel yang berakhir paling awal tidak pernah mengurangi jumlah interval yang dapat Anda pertahankan.

Tangani Batas Sentuhan

Tentukan apakah [1, 2] dan [2, 3] dianggap tumpang tindih. Jika berbagi hanya titik ujung diperbolehkan, gunakan start >= last_end sebagai pengujian.

Algoritma Rakus Lengkap

Urutkan berdasarkan waktu berakhir, lakukan satu kali penyapuan, dan hitung konflik. Total biayanya adalah O(n log n) dari pengurutan ditambah satu lintasan linear.

removed = 0; last_end = float('-inf')
for s, e in intervals:
    if s >= last_end: last_end = e
    else: removed += 1

Pola yang Umum

Pola ini menjadwalkan rapat sebanyak mungkin dalam satu ruangan atau menempatkan pekerjaan sebanyak mungkin pada satu mesin. Kenali pola ini setiap kali konflik harus diminimalkan.

Pemeriksaan Cepat

Anda mempertahankan interval yang tidak tumpang tindih secara rakus.

Ringkasan

Penghapusan minimum sama dengan n dikurangi jumlah yang paling banyak dapat Anda pertahankan. Urutkan berdasarkan waktu berakhir, pertahankan secara rakus interval kompatibel yang berakhir paling awal, lalu hitung sisanya. 🚀

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Penghapusan Minimum agar Tidak Tumpang Tindih” gratis?

Ya — teks lengkap “Penghapusan Minimum agar Tidak Tumpang Tindih” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Penghapusan Minimum agar Tidak Tumpang Tindih”?

Penjadwalan greedy dengan mempertahankan interval yang selesai paling awal Kamu berlatih Competitive Programming Academy 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 Competitive Programming Academy?

Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy 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 4 dari 4.

Berapa lama pelajaran “Penghapusan Minimum agar Tidak Tumpang Tindih” 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 Competitive Programming Academy ini?

Ya. Setiap pelajaran Competitive Programming Academy 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

  1. Mengurutkan Interval Berdasarkan Awal
  2. Menggabungkan Interval yang Tumpang Tindih
  3. Line Sweep untuk Tumpang Tindih Maksimum
  4. Penghapusan Minimum agar Tidak Tumpang Tindih
← Kembali ke Competitive Programming Academy