Meeting Rooms II

Q: 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.

OrtaAralıklar Yığın (heap)Sıralama

+10

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

minMeetingRooms(starts: integer-array, ends: integer-array) → integer

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 ≤ 5000
0 ≤ starts[i] < ends[i] ≤ 10⁶
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 3 odaya ihtiyacın var. Üç oda yeterlidir: 7'den 9'a kadar olan toplantı, 5'te boşalan odayı kullanı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 2 oda yeterlidir.

Ek soru

Her toplantının hangi odaya gittiğini de, yanıttakinden daha fazla oda kullanmadan söyleyebilir misin?

Çö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ı i için running değerini 0 olarak ayarla.
Her bir toplantı j için starts[j] ≤ starts[i] < ends[j] olduğunda running değerine 1 ekle.
Gördüğün en büyük running değ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 most

Odaları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.
rooms ve ended değerlerini 0 olarak ayarlayın.
Her başlangıç zamanı için, sırayla, bu zaman endTimes[ended] değerine eşit veya ondan sonraysa ended değerini 1 artırın: toplantı boşalan bir odayı kullanır.
Aksi hâlde rooms değerini 1 artırın.
rooms değ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 > end yerine start ≥ end kontrolü 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 sorular3

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.

def minMeetingRooms(starts, ends):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

starts = [4, 1, 7, 2]
ends = [8, 5, 9, 6]

Beklenen Çıktı

Meeting Rooms II

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her başlangıçta çalışan toplantıları say

Odaların boşaldığı zamanların min-yığını

Başlangıçları ve bitişleri ayrı ayrı sırala

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler