Non-overlapping Intervals
i aralığı starts[i] noktasından ends[i] noktasına kadar uzanır. Geriye kalan aralıkların hiçbiri birbiriyle çakışmayacak şekilde kaldırmanız gereken en az aralık sayısını döndürün. Biri diğerinin başladığı tam noktada biten ve yalnızca birbirine değen iki aralık çakışmaz.
Fonksiyon
- startsinteger-array
- her aralığın başlangıcı
- endsinteger-array
- her aralığın sonunda, 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ğildir. İ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]'dir. Yalnızca uç noktaları çakışan [2,3] ve [3,6] aralıklarını tutun, diğer 2 aralığı çıkarın. Üçü birden kalamaz: [1,4], [2,3] ile örtüşür ve [3,6], [5,7] ile örtüşür.
- Girdi
- starts = [0, 0, 0]ends = [5, 5, 5]
- Çıktı
- 2
- Açıklama
- Üç aralığın da sınırları [0,5] olduğundan, herhangi ikisi çakışır. Biri kalır ve
2'yi kaldırırsın.
- Girdi
- starts = [4, 1, 2]ends = [6, 2, 4]
- Çıktı
- 0
- Açıklama
- [1,2], [2,4] ve [4,6] uç uca birleşir ve asla çakışmaz, bu yüzden hiçbir şeyi kaldırmazsın ve cevap
0olur.
Ek soru
Her aralığın bir değeri olduğunu ve çakışmayan aralıklar arasından toplam değeri en yüksek olanı istediğini varsayalım. En önce biten aralığı seçmek hâlâ işe yarar mı?
İ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 diğerlerine en çok yer bırakır. En iyi çözümlerden biri onu her zaman seçer.
Aralıkları bitiş değerine göre sıralayın ve tuttuğunuz son aralığın bitişini hatırlayarak üzerinden geçin. Bu bitiş değerinde veya sonrasında başlayan bir aralığı tutun; diğer tüm aralıklar çıkarılmış sayılır.
Çözüm
En az sayıda aralığı kaldırmak, çakışmayan en fazla sayıda aralığı tutmakla aynıdır: cevap, n eksi bu sayıdır. Açgözlü bir kural, sayıyı O(n log n) süresinde bulur: hâlâ sığan aralıklar arasından her zaman en önce biteni tutun.
Her aralığı tutun veya kaldırın
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Aralıkları başlangıçlarına göre sıralayın ve her biri için tutup tutmayacağınıza karar verin. Bir aralığı yalnızca son tutulan aralığın bitişinde veya sonrasında başlıyorsa tutabilirsiniz; böylece tutulan aralıklar çakışmayan bir zincir oluşturur. Her aralıkta iki seçeneği de deneyin ve daha büyük sayıyı alın; cevap n eksi bu sayıdır.
Her aralık dalları ikiye katlayabilir; bu nedenle n aralık, en fazla 2^n yol demektir. Çakışmayan otuz aralık bile bir milyardan fazla çağrı anlamına gelir ve n en fazla 5000 olur.
Algoritma
- Başlangıçlarına göre sıralayın ve her başlangıcı kendi bitişiyle birlikte tutun.
mostKept(i, last)işlevini tanımlayın:lasten son tutulan aralık olduğunda (-1hiçbiri için),ikonumundan itibaren tutabileceğiniz en fazla aralık sayısı.- Sonu geçince
0döndürün. Aksi hâldemostKept(i+1, last)değerini alın; bu,iaralığını çıkarır. iaralığı,lastaralığının bitişinde veya sonrasında başlıyorsa1 + mostKept(i+1, i)değerini de deneyin ve büyük olanı 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 programlamayla en uzun zincir
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Arama aynı soruyu tekrar tekrar sorar: bu aralıkta biten en uzun zincir ne kadar uzun? Her aralık için bu soruyu bir kez yanıtla. Başlangıç zamanına göre sırala ve chain[i] değerinin, son aralık i olacak şekilde tutabileceğin en fazla aralık sayısı olduğunu kabul et.
i aralığından hemen önce gelebilecek bir aralık, starts[i] anında veya daha önce biter; dolayısıyla daha erken başlar ve sıralı düzende daha önce yer alır. Böylece, bu koşulu sağlayan en iyi j için chain[i] = 1 + chain[j] olur; uygun bir aralık yoksa 1 olur. İlk örnekte değerler 1, 1, 2 ve 2’dir; bu yüzden 2 aralığı tutar ve 2 aralığı çıkarırsın.
İç içe iki döngü n(n-1)/2 kontrol yapar: n = 5000 için yaklaşık 12,5 milyon.
Algoritma
- Her başlangıcı kendi bitişiyle birlikte tutarak aralıkları başlangıç değerine göre sırala.
- Her aralık için
chain[i] = 1ayarla. - Her
iveends[j] ≤ starts[i]koşulunu sağlayan herj < iiçin, daha büyüksechain[i]değerinichain[j]+1olarak ayarla. chainiçindeki en büyük değerin'den çıkar ve sonucu döndür.
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ığı seç
Sezgi
En küçük bitiş noktasına sahip aralığı seçin. En iyi çözümlerden biri bunu içerir: Tutabileceğiniz en büyük kümede en erken biten aralığı bununla değiştirin. Bu aralık daha geç bitmediğinden, tutulan bir sonraki aralığın başlangıcında ya da öncesinde hâlâ sona erer ve küme, çakışma olmadan aynı büyüklükte kalır. Bitişinden önce başlayan her aralık bununla çakışır ve çıkarılmalıdır; geriye kalanlar, bitiş noktasında ya da sonrasında başlayan aralıklar üzerinde aynı problemdir.
İlk örnekte, bitiş noktasına göre sıralandığında [2,3] tutulur, [1,4] çıkarılır, [3,6] tutulur ve [5,7] çıkarılır. Bunun yerine en kısa aralığı tutmak, [1,5], [4,7], [6,10] örneğinde başarısız olur: [4,7] diğer iki aralıkla çakışır ve birini çıkarmak yeterliyken iki aralığın çıkarılmasına yol açar.
Sıralamanın maliyeti O(n log n), taramanın maliyeti ise O(n) olur.
Algoritma
- Aralıkları bitişlerine göre sıralayın ve her bitişi kendi başlangıcıyla birlikte tutun.
- İlk aralığı tutun:
lastEnddeğerini bitişine,removeddeğerini ise0olarak ayarlayın. - Sonraki her aralık için, başlangıcı
lastEnddeğerinde veya sonrasında ise aralığı tutun velastEnddeğerini bitişine ayarlayın. - Aksi takdirde,
removeddeğerini 1 artırın. removeddeğerini döndürün.
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
- Birbirine değen aralıkları çakışıyor kabul etmek.
start ≥ lastEndyerinestart > lastEndkullanıldığında [1,2], [2,4], [4,6] zinciri 0 yerine 1 sonucunu verir. - Başlangıç değerine göre sıralayıp çakışma durumunda önceki aralığı tutmak. Geniş [0,100] aralığı, [1,2], [3,4] ve [5,6] aralıklarını dışarı iter: bir yerine üç aralık kaldırılır.
- Sıralı listedeki her aralığı tutulan son aralık yerine komşusuyla karşılaştırmak. İlk örnekte [3,6], kaldırılmış olan [1,4] aralığının değil, [2,3] aralığının bitişiyle karşılaştırılmalıdır; aksi hâlde sonuç 3 olur.
startsveendslistelerini ayrı ayrı sıralamak. Her bitiş değeri kendi başlangıç değeriyle birlikte kalmalıdır.- Kaldırdığınız aralıkların sayısı yerine tuttuğunuz aralıkların sayısını döndürmek.
Sıkça sorulan sorular3
Örtüşmeyen Aralıkların zaman karmaşıklığı nedir?
Açgözlü çözüm bitiş zamanına göre O(n log n) sıralama yapar ve aralıkları bir kez dolaşır; bu nedenle sıralanmış kopya için O(n) alan kullanarak toplamda O(n log n) zaman alır. Dinamik programlama sürümü O(n²) zaman alır; tutulacak her kümeyi denemek ise O(2^n) zaman alır.
Başlangıç zamanına göre sıralayabilir misin?
Evet, örtüşme durumunda farklı bir kuralla. Aralıkları başlangıçlarına göre sırayla ilerlet; sıradaki aralık, tutulan son aralıkla örtüşüyorsa bir kaldırma say ve bu iki aralıktan hangisi daha önce bitiyorsa onu tut. Aynı sayıda kaldırma işlemiyle ve yine O(n log n) zamanda sonuç verir.
Ç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 çıkarılacak en az sayıda aralığı sorar; bu da n eksi o sayıdır. Aynı açgözlü kural, bitişi en erken olan etkinliği tutmak, her iki problemi de çözer.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def eraseOverlapIntervals(starts, ends):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
starts = [3, 1, 5, 2] ends = [6, 4, 7, 3]
Beklenen Çıktı
2