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 Competitive Programming Academy 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, Competitive Programming Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Competitive Programming Academy 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 Competitive Programming Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Competitive Programming Academy 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. Competitive Programming Academy 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.
Competitive Programming Academy öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Competitive Programming Academy, 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 Competitive Programming Academy dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Competitive Programming Academy 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