Meeting Rooms II
Toplantıların listesini iki dizi olarak alırsın: i numaralı toplantı starts[i] anında başlar ve ends[i] anında biter. Bir oda aynı anda tek bir toplantıya ev sahipliği yapar ve bir toplantı, o odadaki başka bir toplantının bittiği anda başlayabilir.
Tüm toplantılara ev sahipliği yapabilecek en az sayıda odayı döndüren minMeetingRooms adlı bir fonksiyon yaz.
Fonksiyon
- startsinteger-array
- her toplantının başlangıç saati
- endsinteger-array
- her toplantının bitiş zamanı, başlangıç zamanıyla aynı indekste
- Döndürürinteger
- tüm toplantıları barındırabilecek en az sayıda oda
Kısıtlar
1 ≤ starts.length == ends.length ≤ 50000 ≤ starts[i] < ends[i] ≤ 106- Toplantılar sıralanmamıştır. İki toplantı aynı olabilir.
Örnekler
- Girdi
- starts = [4, 1, 7, 2]ends = [8, 5, 9, 6]
- Çıktı
- 3
- Açıklama
- 4. zamanda 1'den 5'e, 2'den 6'ya ve 4'ten 8'e kadar olan toplantıların hepsi devam ediyor; bu yüzden en az
3odaya ihtiyacın var. Üç oda yeterlidir: 7'den 9'a kadar olan toplantı, 5'te boşalan odayı kullanır.
- Girdi
- starts = [12, 10, 14]ends = [14, 12, 16]
- Çıktı
- 1
- Açıklama
- Toplantılar 10'dan 12'ye, 12'den 14'e ve 14'ten 16'ya kadar sürer. Her biri, kendisinden önceki biter bitmez başlar; bu nedenle tek bir oda üçünü de alır.
- Girdi
- starts = [0, 2, 3]ends = [10, 3, 5]
- Çıktı
- 2
- Açıklama
- 0'dan 10'a kadar süren toplantı, tüm süre boyunca bir odayı meşgul eder. 2'den 3'e kadar süren toplantı ikinci bir odaya ihtiyaç duyar ve 3'ten 5'e kadar süren toplantı, boşalır boşalmaz aynı odayı kullanır; dolayısıyla
2oda yeterlidir.
Gönderirken +17 gizli test
Ek soru
Her toplantının hangi odaya gittiğini de, yanıttakinden daha fazla oda kullanmadan söyleyebilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Herhangi bir anda, devam eden her toplantının kendine ait bir odaya ihtiyacı vardır. Günün en yoğun anı, yanıt hakkında sana ne söyler?
Toplantıları başlangıç saatlerine göre sırayla gözden geçir. Bir toplantı başladığında, kontrol etmeye değer tek oda en önce boşalan odadır.
Her odanın bitiş zamanını bir min-heap'te tutun. En küçük bitiş zamanı bir sonraki başlangıç zamanında veya öncesindeyse o oda boştur: bitiş zamanını yeni toplantının bitiş zamanıyla değiştirin. Aksi hâlde yeni bir bitiş zamanı ekleyin. Yığının boyutu cevaptır.
Çözüm
İhtiyacınız olan oda sayısı, aynı anda devam eden toplantıların en yüksek sayısıdır. Her başlangıç saatinde devam eden toplantıları saymak, bunu O(n²) sürede bulur. Sıralama, soruyu gün boyunca tek bir geçişe dönüştürür: odaların boşaldığı zamanları tutan bir min-yığın ya da başlangıç ve bitiş saatlerinden oluşan iki sıralı liste, cevabı O(n log n) sürede verir.
Her başlangıçta çalışan toplantıları say
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Herhangi bir anda devam eden her toplantının kendine ait bir odaya ihtiyacı vardır. Bu yüzden en fazla toplantının aynı anda devam ettiği sayı kadar odaya ihtiyacın vardır. Bu sayı aynı zamanda yeterlidir: toplantılara başlangıç zamanlarına göre oda ver; tüm odalar doluysa yeni bir oda açılır, bu da o anda tam olarak o kadar toplantının devam ettiği anlamına gelir.
Devam eden toplantıların sayısı yalnızca bir toplantı başladığında artar; bu nedenle en yoğun an, bir toplantının başladığı andır. Her toplantı i için starts[j] ≤ starts[i] < ends[j] koşulunu sağlayan toplantıların j sayısını bul: bunlar başlamış ve henüz bitmemiş toplantılardır. Tam olarak starts[i] anında biten bir toplantı sayılmaz, çünkü odası o anda yeniden boşalır.
İlk örnekte, 4. zamanda 1 ile 5 arasındaki, 2 ile 6 arasındaki ve 4 ile 8 arasındaki toplantılar devam ediyor: 3. 7. zamanda yalnızca 4 ile 8 arasındaki ve 7 ile 9 arasındaki toplantılar devam ediyor: 2. En yüksek sayı 3'tür.
n toplantının her biri, n toplantının tamamını tarar. n = 5000 için bu 25 milyon kontrol demektir: C'de saniyenin küçük bir bölümü, Python veya R'de birkaç saniye sürer; n her iki katına çıktığında süre dört katına çıkar.
Algoritma
- Her bir toplantı
iiçinrunningdeğerini0olarak ayarla. - Her bir toplantı
jiçinstarts[j] ≤ starts[i] < ends[j]olduğundarunningdeğerine 1 ekle. - Gördüğün en büyük
runningdeğerini sakla. - Bu en büyük değeri döndür.
def minMeetingRooms(starts, ends):
n = len(starts)
most = 0
for i in range(n):
# how many meetings are running at the moment meeting i starts
running = 0
for j in range(n):
if starts[j] <= starts[i] < ends[j]:
running += 1
most = max(most, running)
return mostOdaların boşaldığı zamanların min-yığını
Sezgi
Odaları, resepsiyondaki bir görevlinin yapacağı gibi tahsis edin. Toplantıları başlangıç saatine göre sırayla ele alın. Her toplantı için önce hangi odanın boşalacağına bakın. Toplantı başladığında oda boşsa toplantıyı o odaya alın. Değilse tüm odalar hâlâ meşguldür, bu yüzden yeni bir oda açın.
Yalnızca o odayı kontrol etmek güvenlidir. İlk boşalacak oda hâlâ meşgulse hepsi meşguldür. Boşsa, boş olan herhangi bir oda diğerleri kadar uygundur: sıradaki toplantılar bu saatte veya daha sonra başlayacağından, şimdi boş olan her oda hepsi için boş kalır.
Odalar arasındaki en erken boşalma saatine ihtiyacınız vardır ve bu saat her toplantıdan sonra değişir. Bir min-yığın, her oda için bir bitiş saati tutar ve en küçüğünü verir. Bir odayı yeniden kullanmak, bitiş saatini yeni toplantının bitiş saatiyle değiştirir; yeni bir oda açmak ise yeni bir bitiş saati ekler. İlk örnekte, başlangıç saatine göre sıralandığında: 1'den 5'e [5] verir, 2'den 6'ya [5, 6] verir, 4'ten 8'e [5, 6, 8] verir ve 7'den 9'a toplantısı 5'i 7'den önce veya 7'de bulup değiştirir; geriye [6, 8, 9] kalır. Üç oda.
Sıralama O(n log n) maliyetindedir ve her toplantı, O(log n) maliyetli bir yığın işlemi yapar. Python'daki heapq, Java'daki PriorityQueue, greater ile C++'taki priority_queue, Reverse ile Rust'taki BinaryHeap, Go'daki container/heap ve PHP'deki SplMinHeap yığını sağlar. Diğer dillerde bunu bir dizide tutarsınız: i indeksinin ebeveyni (i-1)/2 konumundadır ve bir değer, ebeveyninden küçük olduğu sürece yukarı çıkar.
Algoritma
- Toplantıları başlangıç zamanlarına göre sıralayın ve her başlangıç zamanını kendi bitiş zamanıyla birlikte tutun.
- Her toplantı için, yığın boş değilse ve en küçük bitiş zamanı toplantının başlangıç zamanında veya daha önceyse, bu bitiş zamanını toplantının bitiş zamanıyla değiştirin.
- Aksi takdirde toplantının bitiş zamanını ekleyin: yeni bir oda açılır.
- Oda başına bir girdi olacak şekilde yığının boyutunu döndürün.
import heapq
def minMeetingRooms(starts, ends):
meetings = sorted(zip(starts, ends)) # by start time
free_at = [] # a min-heap: when each room's last meeting ends
for start, end in meetings:
if free_at and free_at[0] <= start:
heapq.heapreplace(free_at, end) # the earliest free room is free now: reuse it
else:
heapq.heappush(free_at, end) # every room is busy: open a new one
return len(free_at)Başlangıçları ve bitişleri ayrı ayrı sırala
Sezgi
Yığın, hangi bitiş zamanının hangi odaya ait olduğunu hatırlar, ancak yanıt yalnızca bir sayıdır. Bir toplantı başladığında önemli olan tek şey, o zamana kadar herhangi bir toplantının bitip bir odayı boşaltıp boşaltmadığıdır; hangi toplantı olduğu önemli değildir. Bu yüzden başlangıçları ve bitişleri iki ayrı liste olarak sıralayın ve bitişler içinde ended işaretçisiyle başlangıçları sırayla gezin.
Sıradaki her başlangıç için: başlangıç endTimes[ended] zamanında veya sonrasında ise o zamana kadar bir toplantı bitmiştir. Odasını yeni toplantı alır ve ended ilerler. Aksi takdirde kullanılan tüm odalar hâlâ doludur ve rooms bir artar. Her başlangıç en fazla bir bitişi kullanır; tıpkı yığında yeniden kullanılan bir odanın eski bir bitişi yeni bir bitişle değiştirmesi gibi.
İlk örnekte başlangıçlar 1, 2, 4, 7; bitişler ise 5, 6, 8, 9'dur. 1, 2 ve 4 başlangıçlarının tümü 5 bitişinden önce gelir, bu yüzden rooms 3'e yükselir. 7 başlangıcı 5 zamanında veya sonrasında olduğundan o odayı yeniden kullanır ve ended, 6 bitişine ilerler. Yanıt 3'tür. Toplantıların aynı odayı paylaşabildiği durum ≥ ile belirtilir: ikinci örnekte 12 başlangıcı, 12 bitişine denk gelir ve odayı yeniden kullanır.
Sayı hiçbir zaman gerçek tepe değeri aşmaz: rooms arttığında, sıradaki bitiş hâlâ gelecektedir; bu nedenle o anda rooms toplantının tümü sürmektedir. Ayrıca tepe değerine ulaşır; çünkü bir başlangıç, yalnızca o zamana kadar gerçekten bir bitiş odayı boşalttığında yeni bir oda açmayı atlar. İki sıralama işlemi O(n log n), gezinme O(n), sıralanmış kopyalar ise O(n) alan gerektirir.
Algoritma
- Başlangıçların bir kopyasını ve bitişlerin bir kopyasını sıralayın.
roomsveendeddeğerlerini0olarak ayarlayın.- Her başlangıç zamanı için, sırayla, bu zaman
endTimes[ended]değerine eşit veya ondan sonraysaendeddeğerini 1 artırın: toplantı boşalan bir odayı kullanır. - Aksi hâlde
roomsdeğerini 1 artırın. roomsdeğerini döndürün.
def minMeetingRooms(starts, ends):
start_times = sorted(starts)
end_times = sorted(ends)
rooms = 0
ended = 0 # how many meetings have ended, earliest end first
for start in start_times:
if start >= end_times[ended]:
ended += 1 # a meeting has ended by now: this one takes its room
else:
rooms += 1 # every room is busy: open a new one
return rooms
Tuzaklar ve uç durumlar
Hataların çoğu, toplantıların birbirine değdiği andaki karşılaştırmada veya hangi odanın kontrol edildiğinde yapılır.
start > endyerinestart ≥ endkontrolü yapmak. Böylece bir toplantı, oda boşaldığı anda o odayı kullanamaz ve 10 ile 12, 12 ile 14 ve 14 ile 16 arasındaki toplantılar 1 yerine 2 oda gerektirir.- İlk boşalan oda yerine en son açtığınız odayı kontrol etmek. 1 ile 3, 2 ile 10 ve 4 ile 6 arasındaki toplantılar için en son açılan oda 10'a kadar doludur; bu yüzden ilk oda 3'ten beri boş olmasına rağmen üçüncü bir oda açarsınız.
- Bir toplantıyla çakışan en fazla toplantı sayısına 1 eklemek. 0 ile 10 arasındaki toplantı, 2 ile 3 ve 3 ile 5 arasındaki toplantılarla çakışır; ancak bu iki toplantı birbiriyle çakışmadığı için 3 değil, 2 oda yeterlidir.
- Sıralanmış iki yaklaşımı birbirine karıştırmak. Yığın yaklaşımında, başlangıca göre sıralamadan önce her bitiş saati kendi başlangıç saatiyle eşleştirilmelidir; iki liste yaklaşımında ise başlangıçlar ve bitişler özellikle ayrı ayrı sıralanır.
Sıkça sorulan sorular4
Meeting Rooms II'nin zaman karmaşıklığı nedir?
Her iki hızlı çözüm de O(n log n) sürede çalışır. Yığın sürümü toplantıları sıralar ve her toplantı için bir O(log n) yığın işlemi yapar; iki liste sürümü ise iki sıralama ve bir O(n) tarama yapar. Her ikisi de O(n) ek alan kullanır. Her başlangıç zamanında devam eden toplantıları saymak O(n²) sürer.
min-heap, Meeting Rooms II sorununu neden çözer?
Toplantıları başlangıç sırasına göre ele alırken kontrol etmeye değer tek oda, ilk boşalan odadır. Bitiş zamanlarından oluşan bir min-heap, bu odayı O(1) zamanda bulmanı ve O(log n) zamanda güncellemeni sağlar. Heap yalnızca tüm odalar meşgulken büyür; bu nedenle son boyutu, gereken en az oda sayısıdır.
Meeting Rooms II yığın olmadan çözülebilir mi?
Evet. Başlangıç zamanlarını ve bitiş zamanlarını iki ayrı liste olarak sıralayın ve başlangıçlarda, bitişler listesindeki bir işaretçiyle ilerleyin. Kullanılmamış sıradaki bitiş zamanında veya sonrasında başlayan bir toplantı aynı odayı kullanır; diğer tüm başlangıçlar yeni bir oda açar. Aynı fikir bir tarama çizgisi olarak da uygulanabilir: her toplantıyı başlangıcında +1, bitişinde -1 olan bir olaya dönüştürün, eşit zamanlarda önce bitişleri işleyin ve en büyük kümülatif toplamı takip edin.
Yanıt, aynı anda çakışan en fazla toplantı sayısıyla aynı mı?
Evet. Aynı anda gerçekleşen toplantılar için farklı odalar gerekir; bu nedenle en az o kadar odaya ihtiyacın vardır. Her toplantıya başlangıç sırasına göre boş olan herhangi bir odayı vermek hiçbir zaman daha fazlasını gerektirmez; dolayısıyla çakışan toplantıların en yüksek sayısı tam olarak cevaptır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def minMeetingRooms(starts, ends):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
starts = [4, 1, 7, 2] ends = [8, 5, 9, 6]
Beklenen
3