Meeting Rooms II

Q: Jaka jest złożoność czasowa problemu Meeting Rooms II?

Oba szybkie rozwiązania działają w czasie O(n log n) . Wersja z kopcem sortuje spotkania i wykonuje jedną operację na kopcu o złożoności O(log n) dla każdego spotkania; wersja z dwiema listami wykonuje dwa sortowania i jeden przebieg o złożoności O(n) . Oba rozwiązania używają dodatkowej pamięci O(n) . Zliczanie trwających spotkań przy każdym rozpoczęciu ma złożoność O(n²) .

ŚredniePrzedziały Kopiec Sortowanie

+10

Otrzymujesz listę spotkań w postaci dwóch tablic: spotkanie i trwa od starts[i] do ends[i]. W jednej sali może odbywać się tylko jedno spotkanie naraz, a spotkanie może rozpocząć się w sali dokładnie w chwili zakończenia innego spotkania.

Napisz funkcję o nazwie minMeetingRooms, która zwraca najmniejszą liczbę sal, w których można pomieścić wszystkie spotkania.

Funkcja

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

startsinteger-array: godzina rozpoczęcia każdego spotkania
endsinteger-array: czas zakończenia każdego spotkania, pod tym samym indeksem co jego czas rozpoczęcia
Zwracainteger: najmniejsza liczba sal, w których można pomieścić wszystkie spotkania

Ograniczenia

1 ≤ starts.length == ends.length ≤ 5000
0 ≤ starts[i] < ends[i] ≤ 10⁶
Spotkania nie są posortowane. Dwa spotkania mogą być identyczne.

Przykłady

Wejście: starts = [4, 1, 7, 2]ends = [8, 5, 9, 6]
Wyjście: 3
Wyjaśnienie: W chwili 4 trwają wszystkie spotkania: od 1 do 5, od 2 do 6 i od 4 do 8, więc potrzebujesz co najmniej 3 sal. Trzy wystarczą: spotkanie od 7 do 9 odbywa się w sali, która zwalnia się o 5.

Wejście: starts = [0, 2, 3]ends = [10, 3, 5]
Wyjście: 2
Wyjaśnienie: Spotkanie od 0 do 10 zajmuje jedną salę przez cały czas. Spotkanie od 2 do 3 wymaga drugiej sali, a spotkanie od 3 do 5 zajmuje tę samą salę, gdy się zwalnia, więc wystarczą 2 sale.

+17 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy możesz też określić, do której sali trafia każde spotkanie, używając nie więcej sal niż wynika z odpowiedzi?

Rozwiązanie

Liczba potrzebnych sal to największa liczba spotkań odbywających się w tym samym czasie. Zliczenie trwających spotkań przy każdym czasie rozpoczęcia pozwala ją znaleźć w O(n²). Sortowanie zmienia to zadanie w jeden przebieg przez dzień: kopiec minimalny z godzinami, w których zwalniają się sale, albo dwie posortowane listy godzin rozpoczęcia i zakończenia pozwalają uzyskać odpowiedź w O(n log n).

Policz spotkania odbywające się w każdym momencie rozpoczęcia

Poprawne, ale nie kończy się na największych testach

Intuicja

W dowolnym momencie każde trwające spotkanie potrzebuje własnej sali. Potrzebujesz więc co najmniej tylu sal, ile wynosi największa liczba spotkań odbywających się jednocześnie. Tyle sal wystarczy: przydzielaj je według czasu rozpoczęcia, a nowa sala będzie potrzebna tylko wtedy, gdy wszystkie pozostałe są zajęte, co oznacza, że właśnie wtedy odbywa się tyle spotkań.

Liczba trwających spotkań zwiększa się tylko wtedy, gdy rozpoczyna się spotkanie, więc najbardziej obciążony moment przypada na początek któregoś spotkania. Dla każdego spotkania i policz spotkania j, dla których starts[j] ≤ starts[i] < ends[j]: już się rozpoczęły i jeszcze się nie skończyły. Spotkanie, które kończy się dokładnie o starts[i], nie jest liczone, ponieważ w tym momencie jego sala znów jest wolna.

W pierwszym przykładzie o godzinie 4 trwają spotkania od 1 do 5, od 2 do 6 i od 4 do 8: 3. O godzinie 7 trwają tylko spotkania od 4 do 8 i od 7 do 9: 2. Największa liczba to 3.

Dla każdego z n spotkań sprawdzane są wszystkie n spotkania. Przy n = 5000 daje to 25 milionów sprawdzeń: ułamek sekundy w C, kilka sekund w Pythonie lub R, a za każdym razem, gdy n się podwaja, liczba sprawdzeń rośnie czterokrotnie.

Algorytm

Dla każdego spotkania i ustaw running na 0.
Dla każdego spotkania j dodaj 1 do running, gdy starts[j] ≤ starts[i] < ends[j].
Zachowaj największą dotychczas napotkaną wartość running.
Zwróć tę największą wartość.

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

Min-kopiec czasów, w których pokoje stają się wolne

Intuicja

Przydzielaj sale tak, jak zrobiłaby to osoba w recepcji. Rozpatruj spotkania w kolejności według godziny rozpoczęcia. Przy każdym z nich sprawdź salę, która zwolni się najwcześniej. Jeśli będzie wolna przed rozpoczęciem spotkania, spotkanie odbędzie się w tej sali. Jeśli nie, wszystkie sale są nadal zajęte, więc otwierasz nową.

Sprawdzanie tylko tej jednej sali jest bezpieczne. Jeśli sala, która zwolni się najwcześniej, jest nadal zajęta, wszystkie sale są zajęte. Jeśli jest wolna, każda wolna sala jest równie dobra: pozostałe spotkania zaczynają się o tej porze lub później, więc każda sala, która jest teraz wolna, pozostanie wolna dla wszystkich tych spotkań.

Potrzebujesz najwcześniejszej godziny zwolnienia spośród sal, a zmienia się ona po każdym spotkaniu. Kopiec minimalny przechowuje czas zakończenia dla każdej sali i zwraca najmniejszy z nich. Ponowne użycie sali zastępuje jej czas zakończenia czasem zakończenia nowego spotkania; otwarcie sali dodaje nowy czas zakończenia. W pierwszym przykładzie, po posortowaniu według godziny rozpoczęcia: od 1 do 5 daje [5], od 2 do 6 daje [5, 6], od 4 do 8 daje [5, 6, 8], a spotkanie od 7 do 9 znajduje 5, które jest równe 7 lub od niego wcześniejsze, i zastępuje je, pozostawiając [6, 8, 9]. Trzy sale.

Sortowanie kosztuje O(n log n), a każde spotkanie wymaga jednej operacji na kopcu o koszcie O(log n). W Pythonie heapq, w Javie PriorityQueue, w C++ priority_queue z greater, w Rust BinaryHeap z Reverse, w Go container/heap, a w PHP SplMinHeap zapewniają kopiec. W pozostałych językach przechowujesz go w tablicy: rodzic indeksu i znajduje się pod indeksem (i-1)/2, a wartość przesuwa się w górę, dopóki jest mniejsza od swojego rodzica.

Algorytm

Posortuj spotkania według godziny rozpoczęcia, zachowując przyporządkowanie każdej godziny rozpoczęcia do jej godziny zakończenia.
Dla każdego spotkania, jeśli kopiec nie jest pusty, a jego najmniejsza godzina zakończenia przypada o tej samej porze co początek spotkania lub wcześniej, zastąp tę godzinę zakończenia godziną zakończenia spotkania.
W przeciwnym razie dodaj godzinę zakończenia spotkania do kopca: otwiera się nowa sala.
Zwróć rozmiar kopca — jeden wpis na każdą salę.

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)

Posortuj osobno początki i końce

Intuicja

Kopiec przechowuje informacje o tym, który czas zakończenia należy do którego pomieszczenia, ale odpowiedzią jest tylko liczba. Gdy zaczyna się spotkanie, liczy się tylko to, czy jakieś spotkanie zakończyło się do tego momentu i zwolniło pomieszczenie; nie ma znaczenia, które to było spotkanie. Posortuj więc początki i końce na dwóch osobnych listach i przejdź przez początki, używając wskaźnika ended w liście końców.

Dla każdego początku w kolejności: jeśli jest równy lub późniejszy niż endTimes[ended], spotkanie zdążyło się już zakończyć. Jego pomieszczenie zajmuje nowe spotkanie, a ended przechodzi dalej. W przeciwnym razie wszystkie używane pomieszczenia są nadal zajęte, więc rooms zwiększa się o jeden. Każdy początek wykorzystuje najwyżej jeden koniec, tak jak ponownie użyte pomieszczenie w kopcu zamienia jeden stary koniec na jeden nowy.

W pierwszym przykładzie początki to 1, 2, 4, 7, a końce to 5, 6, 8, 9. Początki 1, 2 i 4 przypadają przed końcem 5, więc rooms rośnie do 3. Początek 7 jest równy lub późniejszy niż 5, więc ponownie wykorzystuje to pomieszczenie, a ended przechodzi do końca 6. Odpowiedź to 3. Znak ≥ pozwala na współdzielenie pomieszczenia przez stykające się spotkania: w drugim przykładzie początek 12 przypada w chwili końca 12, więc pomieszczenie zostaje ponownie wykorzystane.

Liczba nigdy nie przekracza rzeczywistego maksimum: gdy rooms rośnie, następny koniec jeszcze nie nastąpił, więc w tej chwili trwa rooms spotkań. Osiąga też to maksimum, ponieważ początek pomija otwarcie pomieszczenia tylko wtedy, gdy rzeczywisty koniec przypada na ten moment lub wcześniej i zwolnił już pomieszczenie. Dwa sortowania kosztują O(n log n), przejście przez listę O(n), a posortowane kopie zajmują O(n) miejsca.

Algorytm

Posortuj kopię czasów rozpoczęcia i kopię czasów zakończenia.
Ustaw rooms i ended na 0.
Dla każdego czasu rozpoczęcia w kolejności, jeśli jest równy lub późniejszy niż endTimes[ended], zwiększ ended o 1: spotkanie zajmuje zwolnioną salę.
W przeciwnym razie zwiększ rooms o 1.
Zwróć rooms.

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

Pułapki i przypadki brzegowe

Większość błędów wynika z porównania w chwili, gdy spotkania stykają się w czasie, albo ze sprawdzania niewłaściwej sali.

Sprawdzanie start > end zamiast start ≥ end. Wtedy spotkanie nie może skorzystać z sali w chwili, gdy się zwalnia, a spotkania od 10 do 12, od 12 do 14 i od 14 do 16 zajmują 2 sale zamiast 1.
Sprawdzanie ostatnio otwartej sali zamiast tej, która zwolni się jako pierwsza. W przypadku spotkań od 1 do 3, od 2 do 10 i od 4 do 6 ostatnio otwarta sala jest zajęta do 10, więc otwierasz trzecią salę, mimo że pierwsza jest wolna już od 3.
Branie największej liczby spotkań, które nakładają się na jedno spotkanie, i dodawanie 1. Spotkanie od 0 do 10 nakłada się na spotkania od 2 do 3 i od 3 do 5, ale te dwa spotkania nie nakładają się na siebie, więc wystarczą 2 sale, a nie 3.
Mylenie dwóch podejść opartych na sortowaniu. W kopcu każdy koniec musi pozostać sparowany z własnym początkiem przed sortowaniem według początku; podejście z dwiema listami celowo sortuje początki i końce osobno.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu Meeting Rooms II?

Oba szybkie rozwiązania działają w czasie O(n log n). Wersja z kopcem sortuje spotkania i wykonuje jedną operację na kopcu o złożoności O(log n) dla każdego spotkania; wersja z dwiema listami wykonuje dwa sortowania i jeden przebieg o złożoności O(n). Oba rozwiązania używają dodatkowej pamięci O(n). Zliczanie trwających spotkań przy każdym rozpoczęciu ma złożoność O(n²).

Dlaczego min-kopiec rozwiązuje problem Meeting Rooms II?

Rozpatrując spotkania w kolejności rozpoczęcia, warto sprawdzić tylko salę, która zwolni się jako pierwsza. Kopiec minimalny czasów zakończenia pozwala znaleźć tę salę w O(1) i aktualizować kopiec w O(log n). Kopiec rośnie tylko wtedy, gdy wszystkie sale są zajęte, więc jego końcowy rozmiar oznacza najmniejszą liczbę potrzebnych sal.

Czy problem „Meeting Rooms II” da się rozwiązać bez kopca?

Tak. Posortuj godziny rozpoczęcia i zakończenia jako dwie osobne listy, a następnie przechodź przez godziny rozpoczęcia, korzystając ze wskaźnika w liście godzin zakończenia. Rozpoczęcie o tej samej godzinie co najbliższe niewykorzystane zakończenie lub później oznacza ponowne użycie sali; każde inne rozpoczęcie wymaga otwarcia nowej sali. Ten sam pomysł działa w przypadku metody linii zamiatania: zamień każde spotkanie na zdarzenie +1 w chwili jego rozpoczęcia i zdarzenie -1 w chwili jego zakończenia, przetwarzaj zakończenia przed rozpoczęciami o tych samych godzinach i śledź największą bieżącą sumę.

Czy odpowiedź jest taka sama jak największa liczba spotkań, które nakładają się na siebie w tym samym czasie?

Tak. Spotkania odbywające się w tym samym czasie wymagają różnych sal, więc potrzebujesz co najmniej tylu sal. Przydzielanie każdemu spotkaniu, w kolejności rozpoczęcia, dowolnej wolnej sali nigdy nie wymaga ich więcej, więc szczytowa liczba nakładających się spotkań jest dokładnie odpowiedzią.

Python

def minMeetingRooms(starts, ends):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

Meeting Rooms II

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Policz spotkania odbywające się w każdym momencie rozpoczęcia

Min-kopiec czasów, w których pokoje stają się wolne

Posortuj osobno początki i końce

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania