Kesişmeme için Minimum Silme
En erken bitişi koruyan açgözlü planlama yapın.
Kesişmeme için Minimum Silme, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 4. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Çıkarma Hedefi
Örtüşen aralıklarınız var ve artık hiçbirinin örtüşmemesi için en az sayıda çıkarma yapmak istiyorsunuz. Mümkün olduğunca çoğunu tutun. ✂️
Soruyu Tersine Çevirin
En az sayıda aralık çıkarmak, örtüşmeyen aralıkların en çoğunu tutmakla aynıdır. Tutma sürümünü çözün; çıkarılacak sayı, n eksi tuttuğunuz sayıdır.
Bu, Etkinlik Seçimidir
Örtüşmeyen aralıkların en çoğunu tutmak, kılık değiştirmiş klasik etkinlik seçimi problemidir. Aynı açgözlü fikir her ikisini de çözer.
Bitişe Göre Sort Edin
Burada en iyi sıralama başlangıca göre değil, bitiş zamanına göredir. Erken bitirmek, tutabileceğiniz bir sonraki aralık için zaman çizelgesini en kısa sürede boşaltır.
intervals.sort(key=lambda x: x[1])Açgözlü Seçim
Hâlâ uyumlu olanlar arasından en erken biten aralığı her zaman tutun. Böylece geri kalanlar için mümkün olan en geniş alanı bırakırsınız.
Son Tutulan Bitişi İzleyin
Tuttuğunuz son aralığın bitişini saklayın. Bir sonraki aralık, yalnızca başlangıcı o sınırda veya sınırdan sonra ise uyumludur.
if start >= last_end:
last_end = endÇıkarmaları Sayın
Bir aralık last_end'den önce başlıyorsa çakışır; bu nedenle onu çıkarın ve çıkarma sayınıza bir ekleyin. Aksi durumda aralığı tutun.
else:
removed += 1En Erken Bitiş Neden Kazanır
Bunu bir takas argümanı kanıtlar: tutulan herhangi bir aralığı uyumlu aralıklar arasından en erken bitenle değiştirmek, tutabileceğiniz aralık sayısını hiçbir zaman azaltmaz.
Temas Durumunu Ele Alın
[1, 2] ve [2, 3] aralıklarının örtüşmüş sayılıp sayılmayacağına karar verin. Yalnızca bir uç noktayı paylaşmaya izin veriliyorsa start >= last_end koşulunu sınama olarak kullanın.
Tam Açgözlü Çözüm
Bitişe göre sort edin, bir kez tarayın ve çakışmaları sayın. Toplam maliyet, sort işleminden gelen O(n log n) ile tek bir doğrusal geçişin toplamıdır.
removed = 0; last_end = float('-inf')
for s, e in intervals:
if s >= last_end: last_end = e
else: removed += 1Tanıdık Bir Yapı
Bu düzen, tek bir odada en çok toplantıyı planlar veya tek bir makinede en çok işi paketler. Çakışmaların en aza indirilmesi gereken her yerde bu yapıyı fark edin.
Hızlı Kontrol
Örtüşmeyen aralıkları açgözlü biçimde tutarsınız.
Özet
En az çıkarma sayısı, tutabileceğiniz en yüksek sayı olan n eksi bu sayıya eşittir. Bitişe göre sort edin, en erken biten uyumlu aralıkları açgözlü biçimde tutun ve geri kalanları sayın. 🚀
Sıkça Sorulan Sorular
“Kesişmeme için Minimum Silme” dersi ücretsiz mi?
Evet — “Kesişmeme için Minimum Silme” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Kesişmeme için Minimum Silme” dersinde ne öğreneceğim?
En erken bitişi koruyan açgözlü planlama yapın. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 4. dersidir.
“Kesişmeme için Minimum Silme” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Aralıkları Başlangıca Göre Sıralama
- Kesişen Aralıkları Birleştirme
- Maksimum Kesişim için Doğru Süpürme
- Kesişmeme için Minimum Silme