Non-overlapping Intervals
Aralıkların listesini iki dizi olarak alırsın: i aralığı starts[i] noktasından ends[i] noktasına kadar uzanır. Geriye kalan aralıklardan hiçbiri çakışmayacak şekilde mümkün olduğunca az aralığı kaldır. Yalnızca birbirine dokunan, yani birinin bittiği noktanın diğerinin başladığı noktayla tam olarak aynı olduğu iki aralık çakışmaz.
Kaldırman gereken en küçük aralık sayısını döndüren eraseOverlapIntervals adlı bir fonksiyon yaz.
Fonksiyon
- startsinteger-array
- her aralığın başlangıcı
- endsinteger-array
- her aralığın bitişi, başlangıcıyla aynı indekste
- Döndürürinteger
- Geriye kalanların çakışmaması için kaldırılması gereken en az aralık sayısı
Kısıtlar
1 ≤ starts.length == ends.length ≤ 5000-5 × 104 ≤ starts[i] < ends[i] ≤ 5 × 104- Aralıklar sıralı değil. İki aralık aynı olabilir.
Örnekler
- Girdi
- starts = [3, 1, 5, 2]ends = [6, 4, 7, 3]
- Çıktı
- 2
- Açıklama
- Başlangıç sırasına göre aralıklar [1,4], [2,3], [3,6] ve [5,7] şeklindedir. Yalnızca uç noktaları çakışan [2,3] ve [3,6] aralıklarını tutun, diğer 2 aralığı kaldırın. Üç aralığı tutamazsınız: [1,4], [2,3] ile çakışır ve [3,6], [5,7] ile çakışır; dört aralıktan seçilecek herhangi üçü bu çiftlerden birini içerir.
- Girdi
- starts = [0, 0, 0]ends = [5, 5, 5]
- Çıktı
- 2
- Açıklama
- Üç aralığın da değeri [0,5] olduğundan, bu aralıklardan herhangi ikisi örtüşür. Yalnızca biri kalabilir; diğer
2tanesini kaldırırsın.
- Girdi
- starts = [4, 1, 2]ends = [6, 2, 4]
- Çıktı
- 0
- Açıklama
- [1,2], [2,4] ve [4,6] bitişleri başlangıçlarına denk gelecek şekilde birleşir ve hiçbir zaman çakışmaz; bu nedenle hiçbirini kaldırmazsın ve yanıt
0olur.
Gönderirken +17 gizli test
Ek soru
Her aralığın bir değeri olduğunu ve çakışmayan aralıklar arasındaki toplam değerin en büyüğünü istediğini varsayalım. En erken biten aralığı tutmak yine işe yarar mı? Bunun yerine ne kullanırdın?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Neyi kaldıracağını seçmek yerine, neyi tutacağını düşün. Tutabileceğin en büyük aralık kümesi, yanıtla nasıl ilişkilidir?
Tüm aralıklar arasında en önce biten, geri kalanlar için en fazla alanı bırakır. En iyi yanıtlardan biri onu her zaman içerir.
Aralıkları bitiş noktalarına göre sırala ve tuttuğun son aralığın bitiş noktasını hatırlayarak aralıklar üzerinde ilerle. Bu bitiş noktasında veya sonrasında başlayan bir aralık tutulur; diğer tüm aralıklar silinmiş sayılır.
Çözüm
En az sayıda aralığı kaldırmak, çakışmayan en fazla sayıda aralığı tutmakla aynıdır; bu nedenle cevap, n eksi bu en büyük kümedir. Tutulacak her kümeyi denemek üstel zaman alır; aralık zincirleri üzerinde dinamik programlama yapmak ise bunu O(n²) düzeyine indirir. Tek bir açgözlü kural işi O(n log n) düzeyinde tamamlar: hâlâ sığan aralıklar arasından her zaman en erken biteni tutun.
Her aralığı tutun veya kaldırın
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Soruyu tersinden düşün. En az sayıda aralığı kaldırmak, çakışmayan en fazla sayıda aralığı tutmak demektir ve yanıt n eksi bu sayıdır. Bu yüzden tutabileceğin en büyük kümeyi ara.
Aralıkları başlangıç noktalarına göre sırala ve sırayla her biri için kaldırmaya mı yoksa tutmaya mı karar ver. Bir aralığı yalnızca tuttuğun son aralığın bitiş noktasında ya da sonrasında başlıyorsa tutabilirsin. Bu tek kontrol yeterlidir: tutulan aralıklar, her birinin kendinden öncekinin bitiş noktasında ya da sonrasında başladığı bir zincir oluşturur; dolayısıyla hiçbiri birbiriyle çakışmaz. Her aralıkta iki seçeneği de dene ve daha iyi sonucu al.
İlk örnekte sıralanmış aralıklar [1,4], [2,3], [3,6], [5,7] şeklindedir. [1,4] aralığını tutmak, 4'ten önce başlayan [2,3] ve [3,6] aralıklarını engeller ve [5,7] için yer bırakır: tutulan 2 aralık. [1,4] aralığını kaldırıp [2,3] aralığını ve ardından [3,6] aralığını tutmak da 2 aralık tutar. Hiçbir dal 3'e ulaşamaz; bu nedenle 4-2 = 2 aralığı kaldırırsın.
Her aralık, dal sayısını ikiye katlayabilir; bu yüzden n aralık en fazla 2^n yol oluşturur. Çakışmayan otuz aralık bile bir milyardan fazla çağrı anlamına gelir ve testlerde 5000 aralığa kadar çıkılır. Özyineleme ayrıca n seviye derinliğe ulaşır: en büyük testlerde 5000 çağrı, Python'ın varsayılan 1.000 sınırını aşar.
Algoritma
- Başlangıçlarına göre aralıkları sıralayın ve her başlangıcı kendi bitişiyle birlikte tutun.
mostKept(i, last)tanımlayın:last, tutulan en son aralığın konumu olduğunda (-1, hiçbiri için),ikonumundan itibaren tutabileceğiniz en fazla aralık sayısı.- Listenin sonunu geçince
0döndürün. Aksi hâldemostKept(i+1, last)ile başlayın; bu,iaralığını kaldırmanın sonucudur. iaralığı,lastaralığının bitişinde veya sonrasında başlıyorsa1 + mostKept(i+1, i)seçeneğini de deneyin ve daha büyük sonucu tutun.neksimostKept(0, -1)değerini döndürün.
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(starts, ends)) # by start time
n = len(intervals)
def most_kept(i, last):
# The most intervals you can keep among i..n-1, when interval last
# is the latest one kept so far (-1: nothing kept yet).
if i == n:
return 0
best = most_kept(i + 1, last) # remove interval i
if last == -1 or intervals[i][0] >= intervals[last][1]:
best = max(best, 1 + most_kept(i + 1, i)) # keep interval i
return best
return n - most_kept(0, -1)Dinamik programlama ile en uzun zincir
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Yukarıdaki arama aynı soruyu tekrar tekrar yanıtlıyor: Bu aralıkla biten en uzun zincir nedir? Bu yanıtı her aralık için bir kez sakla. Başlangıca göre sırala ve chain[i], son tutulan aralık i olduğunda tutabileceğin en fazla aralık sayısı olsun.
i değerinden hemen önce tutulan aralığın, starts[i] değerinde veya daha önce bitmesi gerekir. Böyle her aralık sıralı düzende daha önce gelir: başlangıcı, bitişinden önce olduğundan starts[i] değerinden önce başlar. Bu da ends[j] ≤ starts[i] koşulunu sağlayan en iyi önceki j için chain[i] = 1 + chain[j] sonucunu verir; uygun aralık yoksa değer 1 olur. chain içindeki en büyük değer, tutabileceğin en fazla aralık sayısıdır.
İlk örnek için sıralı liste [1,4], [2,3], [3,6], [5,7] olur ve değerler 1, 1, 2 ve 2'dir: [3,6], [2,3] aralığını izleyebilir ve [5,7], [1,4] veya [2,3] aralığını izleyebilir. En uzun zincir 2 olduğundan 4-2 = 2 aralığı silersin.
Her aralık, kendisinden önceki tüm aralıkları kontrol eder; bu da n(n-1)/2 kontrol demektir. n = 5000 için bu yaklaşık 12,5 milyon kontroldür: derlenen bir dilde sorun olmaz, en büyük testlerde daha yavaş diller için fazla yavaştır ve aşağıdaki açgözlü algoritmadan çok daha kötüdür.
Algoritma
- Aralıkları başlangıçlarına göre sıralayın ve her başlangıcı kendi bitişiyle birlikte tutun.
- Her aralık için
chain[i] = 1olarak ayarlayın. - Her
iiçin veends[j] ≤ starts[i]koşulunu sağlayan herj < iiçin, daha büyüksechain[i]değerinichain[j]+1olarak ayarlayın. ndeğerindenchainiçindeki en büyük değeri çıkarıp sonucu döndürün.
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(starts, ends)) # by start time
n = len(intervals)
# chain[i]: the most intervals you can keep when interval i is the last one kept
chain = [1] * n
for i in range(n):
for j in range(i):
if intervals[j][1] <= intervals[i][0] and chain[j] + 1 > chain[i]:
chain[i] = chain[j] + 1
return n - max(chain)Açgözlü: En önce biten aralığı tut
Sezgi
En küçük bitiş değerine sahip aralığa bak. En iyi yanıtlardan biri onu her zaman korur. Koruyabileceğin en büyük aralıklardan herhangi bir kümesini al ve en erken aralığını bununla değiştir. Yeni aralık, değiştirdiği aralıktan daha geç bitmez; dolayısıyla korunan sonraki aralığın başlangıcında veya öncesinde biter. Küme örtüşmesiz kalır ve boyutunu korur; bu nedenle en erken bitişi korumak sana hiçbir şeye mal olmaz.
Onu koruduktan sonra, bitişinden önce başlayan her aralık onunla örtüşür ve çıkarılmalıdır. Geriye kalan, bu bitişte veya sonrasında başlayan aralıklar üzerinde aynı sorudur; bu yüzden aynı kuralı yeniden uygula. Pratikte: bitişe göre sırala, listeyi tara ve korunan son aralığın bitişi olan lastEnd değerini hatırla. lastEnd değerinde veya sonrasında başlayan bir aralığı koru; diğer her aralığı çıkarılmış olarak say.
Bitişe göre sıralanmış ilk örnek [2,3], [1,4], [3,6], [5,7] şeklindedir. [2,3] aralığını koru; böylece lastEnd = 3 olur. [1,4], 3'ten önce olan 1'de başlar: onu çıkar. [3,6], 3'ten önce değil, 3'te başlar: onu koru; lastEnd = 6 olur. [5,7], 6'dan önce olan 5'te başlar: onu çıkar. İki aralık çıkarıldı.
Diğer ölçütler cazip görünür ama işe yaramaz. Başlangıca göre sıralamak, [1,2], [3,4] ve [5,6] aralıklarını kapsarken [0,100] aralığını korur ve bir yerine üç aralığı çıkarır. En kısa aralığı korumak da [1,5], [4,7], [6,10] örneğinde işe yaramaz: kısa olan [4,7], diğer iki aralıkla örtüşür; bu yüzden onu korumak, bir çıkarma yeterliyken iki aralığı çıkarmana neden olur. Bitiş, sonrasındaki her şey için en fazla alanı bırakan ölçüttür.
Sıralama O(n log n), listeyi tarama ise O(n) maliyetindedir. Aralıkların sıralanmış kopyası O(n) alan kullanır.
Algoritma
- Aralıkları, her bitişi kendi başlangıcıyla birlikte tutarak bitişe göre sırala.
- İlk aralığı koru:
lastEnddeğerini bitişine,removeddeğerini ise0olarak ayarla. - Sonraki her aralık için, başlangıcı
lastEnddeğerine eşit veya daha büyükse aralığı koru velastEnddeğerini bitişine ayarla. - Aksi takdirde
removeddeğerini 1 artır. removeddeğerini döndür.
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(ends, starts)) # by end time
removed = 0
last_end = intervals[0][0] # the interval that ends first is always kept
for end, start in intervals[1:]:
if start >= last_end:
last_end = end # it fits after the last kept interval: keep it
else:
removed += 1 # it overlaps the last kept interval: remove it
return removed
Tuzaklar ve uç durumlar
Yanlış yanıtların çoğu sıralama anahtarından veya aralıkların uç uca geldiği noktadaki karşılaştırmadan kaynaklanır.
- Uç uca gelen aralıkları çakışıyor kabul etmek.
start ≥ lastEndyerinestart > lastEndkullanıldığında, [1,2], [2,4], [4,6] zincirinde [1,2] aralığının bittiği yerde başlayan [2,4] aralığı kaldırılır ve yanıt 0 yerine 1 çıkar. - Başlangıca göre sıralayıp çakışma olduğunda her zaman daha önce başlayan aralığı tutmak. Geniş [0,100] aralığı, ardından [1,2], [3,4] ve [5,6] aralıklarını eler. Başlangıca göre sıralıyorsanız, çakışan iki aralıktan hangisi önce bitiyorsa onu tutun.
- Sıralı listedeki her aralığı son tutulan aralık yerine komşusuyla karşılaştırmak. [1,4] aralığını kaldırdıktan sonra, sonraki aralık 4 ile değil, [2,3] aralığının bitişiyle karşılaştırılmalıdır.
startsveendsdeğerlerini iki ayrı liste olarak sıralamak. Her bitiş kendi başlangıcıyla birlikte kalmalıdır; aksi hâlde bir başlangıcı başka bir aralığın bitişiyle karşılaştırırsınız.- Tuttuğunuz aralıkların sayısını döndürmek. Soru, kaldırılan aralıkların sayısını sorar; bu da
neksi tutulan aralıkların sayısıdır.
Sıkça sorulan sorular4
Çakışmayan Aralıklar probleminin zaman karmaşıklığı nedir?
Açgözlü çözüm, aralıkları bitiş zamanına göre O(n log n) içinde sıralar ve ardından üzerlerinde bir kez O(n) içinde gezinir; dolayısıyla toplam süre O(n log n) olur. Aralıkların sıralanmış kopyası O(n) alan kullanır. Dinamik programlama sürümü O(n²) sürer ve tutulacak her kümeyi denemek O(2^n) sürer.
Bitiş zamanına göre sıralamak neden en az sayıda kaldırma işlemi sağlar?
İlk biten aralık, çakışma oluşturmadan herhangi bir en iyi yanıtın ilk aralığının yerini alabilir; çünkü daha geç bitmez. Dolayısıyla en iyi yanıtlardan biri bu aralığı içerir ve onunla çakışan her şeyi çıkardıktan sonra geriye kalan, daha küçük bir küme üzerindeki aynı problemdir. Bu argümanı tekrarlamak, her açgözlü seçimin güvenli olduğunu gösterir.
Başlangıç saatine göre sıralayabilir misin?
Evet, örtüşme için farklı bir kuralla. Aralıkları başlangıçlarına göre dolaş ve sıradaki aralık son tutulan aralıkla örtüştüğünde bir silme say ve bu ikisinden önce biteni tut. Bitişlere göre sıralamayla aynı sayıda aralık siler ve aynı O(n log n) sürede çalışır.
Çakışmayan Aralıklar, etkinlik seçimi problemiyle aynı mıdır?
Bu, bunun diğer yüzüdür. Etkinlik seçimi, çakışmayan en fazla sayıda aralığı bulmayı ister; bu problem ise kaldırılacak en az sayıda aralığı ister; bu da n eksi o sayıdır. Aynı açgözlü kural, en önce biten etkinliği tutmak, her iki problemi de çözer.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def eraseOverlapIntervals(starts, ends):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
starts = [3, 1, 5, 2] ends = [6, 4, 7, 3]
Beklenen
2