Meeting Rooms

Q: Jaka jest złożoność czasowa problemu sal konferencyjnych?

Sortowanie spotkań według godziny rozpoczęcia kosztuje O(n log n) , a przejście porównujące sąsiednie elementy ma złożoność O(n) , więc łączna złożoność wynosi O(n log n) . Porównanie każdej pary kosztuje natomiast O(n²) .

Q: Dlaczego wystarczy porównać każde spotkanie z poprzednim?

Po posortowaniu według czasu rozpoczęcia, jeśli dotąd nie wykryto żadnego konfliktu, dotychczasowe spotkania tworzą ciąg, w którym każde rozpoczyna się w chwili zakończenia poprzedniego lub później. Ostatnie spotkanie w tym ciągu kończy się najpóźniej. Nowe spotkanie, które rozpoczyna się w chwili jego zakończenia lub później, nie może nakładać się na żadne z wcześniejszych spotkań.

Q: Czy spotkania, które tylko się stykają, nakładają się na siebie?

Nie w tym zadaniu: spotkanie może rozpocząć się dokładnie w chwili, gdy kończy się inne. Dlatego sprawdzenie ma postać ścisłej nierówności start < previous end . Gdyby spotkania stykające się w czasie były niedozwolone, sprawdzenie miałoby postać start ≤ previous end .

Q: Jak znaleźć minimalną liczbę sal konferencyjnych?

Posortuj godziny rozpoczęcia i godziny zakończenia jako dwie oddzielne listy, a następnie przejdź przez obie: każde rozpoczęcie otwiera salę, a każde zakończenie, które następuje przed następnym rozpoczęciem lub w tej samej chwili, zwalnia jedną salę. Odpowiedzią jest największa liczba sal jednocześnie zajętych. Odpowiedź na pytanie tak lub nie jest tu równoznaczna z pytaniem, czy wystarczy jedna sala.

ŁatwePrzedziały Sortowanie

+10

Otrzymujesz listę spotkań w postaci dwóch tablic: spotkanie i trwa od starts[i] do ends[i]. Jedna osoba chce uczestniczyć we wszystkich, więc żadne dwa spotkania nie mogą się nakładać. Spotkanie może rozpocząć się dokładnie w chwili zakończenia innego. Zwróć true, jeśli ta osoba może uczestniczyć we wszystkich spotkaniach, a w przeciwnym razie false.

Funkcja

canAttendMeetings(starts: integer-array, ends: integer-array) → boolean

startsinteger-array: czas rozpoczęcia każdego spotkania
endsinteger-array: czas zakończenia każdego spotkania, pod tym samym indeksem co jego rozpoczęcie
Zwracaboolean: prawda, jeśli żadne dwa spotkania się nie nakładają, w przeciwnym razie fałsz

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 = [9, 13, 10]ends = [10, 15, 12]
Wyjście: true
Wyjaśnienie: Spotkania w kolejności czasowej odbywają się od 9 do 10, od 10 do 12 i od 13 do 15. Drugie zaczyna się w chwili, gdy kończy się pierwsze, co jest dozwolone, więc odpowiedź to true.

Wejście: starts = [1, 4, 7]ends = [5, 6, 8]
Wyjście: false
Wyjaśnienie: Spotkanie od 1 do 5 nadal trwa o 4, gdy rozpoczyna się spotkanie od 4 do 6, więc odpowiedź to false.

+15 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Jeśli spotkania są rezerwowane pojedynczo, jak sprawdzać każdą nową rezerwację względem harmonogramu w O(log n), bez ponownego sortowania wszystkiego?

Rozwiązanie

Sprawdzenie każdej pary spotkań pozwala wykryć wszystkie konflikty, ale wymaga O(n²). Sortowanie według czasu rozpoczęcia zmienia podejście: spotkanie może wtedy kolidować tylko z sąsiednim spotkaniem w posortowanej kolejności, więc wystarczy jedno porównanie na spotkanie.

Porównaj każdą parę

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

Intuicja

Dwa spotkania kolidują, gdy każde z nich zaczyna się przed zakończeniem drugiego. W przypadku spotkań od 1 do 5 i od 4 do 6: 1 jest przed 6, a 4 jest przed 5, więc kolidują. W przypadku spotkań od 9 do 10 i od 10 do 12: 10 nie jest przed 10, więc tylko stykają się ze sobą.

Zastosowanie ścisłego < po obu stronach pozwala rozpocząć spotkanie dokładnie w chwili zakończenia innego. Uruchom test dla każdej pary i zwróć false przy pierwszej kolizji.

Problemem jest liczba par. Dla n = 5000 spotkań jest ich około 12,5 miliona, a harmonogram bez kolizji wymusza sprawdzenie ich wszystkich, co jest zbyt wolne dla największych testów.

Algorytm

Dla każdego indeksu i i każdego indeksu j znajdującego się po nim:
Jeśli starts[i] < ends[j] i starts[j] < ends[i], te dwa spotkania nakładają się: zwróć false.
Jeśli żadna para się nie nakłada, zwróć true.

def canAttendMeetings(starts, ends):
    n = len(starts)
    for i in range(n):
        for j in range(i + 1, n):
            # two meetings clash when each one starts before the other ends
            if starts[i] < ends[j] and starts[j] < ends[i]:
                return False
    return True

Sortuj według początku i sprawdź sąsiadów

Intuicja

Posortuj spotkania według czasu rozpoczęcia, zachowując każde rozpoczęcie razem z odpowiadającym mu zakończeniem. Teraz przyjrzyj się dowolnemu spotkaniu i temu, które odbywa się bezpośrednio przed nim. Jeśli wcześniejsze kończy się po rozpoczęciu późniejszego, spotkania kolidują. W przeciwnym razie późniejsze spotkanie rozpoczyna się w chwili zakończenia wcześniejszego lub później.

Dlaczego wystarczy sprawdzić tylko sąsiednie spotkanie? Jeśli każde dotychczasowe spotkanie rozpoczyna się w chwili zakończenia poprzedniego lub później, dotychczasowe spotkania nigdy się nie nakładają, a to bezpośrednio poprzedzające kończy się najpóźniej. Nowe spotkanie, które rozpoczyna się w chwili jego zakończenia lub później, rozpoczyna się w chwili zakończenia każdego z nich lub później.

W pierwszym przykładzie posortowane spotkania to: od 9 do 10, od 10 do 12, od 13 do 15. Rozpoczęcie o 10 nie następuje przed zakończeniem o 10, a rozpoczęcie o 13 nie następuje przed zakończeniem o 12, więc spotkania nie kolidują. Jednakowe czasy rozpoczęcia zawsze oznaczają kolizję, ponieważ każde spotkanie trwa co najmniej jedną jednostkę czasu, a to sprawdzenie również je wykrywa.

Sortowanie kosztuje O(n log n), a przejście po danych — O(n). Sparowana kopia spotkań zajmuje O(n) pamięci.

Algorytm

Dopasuj każdy początek do jego końca.
Posortuj pary według czasu rozpoczęcia.
Dla każdego spotkania po pierwszym porównaj jego czas rozpoczęcia z czasem zakończenia poprzedniego spotkania.
Jeśli czas rozpoczęcia jest wcześniejszy, zwróć false.
Po pętli zwróć true.

def canAttendMeetings(starts, ends):
    meetings = sorted(zip(starts, ends))  # by start time
    for i in range(1, len(meetings)):
        # a meeting must not start before the one right before it ends
        if meetings[i][0] < meetings[i - 1][1]:
            return False
    return True

Pułapki i przypadki brzegowe

Typowe błędy dotyczą tego, które końce są ze sobą porównywane i jak traktowane są stykające się spotkania.

Sortowanie starts i pozostawienie ends w kolejności z danych wejściowych. Każdy koniec musi pozostać powiązany z własnym początkiem, w przeciwnym razie porównasz początek z końcem innego spotkania.
Używanie ≤ zamiast <. Spotkania od 9 do 10 i od 10 do 12 stykają się, ale nie nakładają na siebie, więc odpowiedzią dla nich jest true.
Sprawdzanie wyłącznie, czy każde spotkanie kończy się przed rozpoczęciem następnego w kolejności z danych wejściowych. Dane wejściowe nie są posortowane, więc sąsiednie elementy w danych wejściowych niczego nie mówią.
Zapisanie testu dla pary za pomocą jednego warunku, takiego jak starts[j] < ends[i]. Jest on poprawny tylko wtedy, gdy spotkanie j zaczyna się później; dla spotkań od 5 do 6 i od 0 do 1, w tej kolejności, 0 < 6 zgłasza konflikt, którego nie ma.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu sal konferencyjnych?

Sortowanie spotkań według godziny rozpoczęcia kosztuje O(n log n), a przejście porównujące sąsiednie elementy ma złożoność O(n), więc łączna złożoność wynosi O(n log n). Porównanie każdej pary kosztuje natomiast O(n²).

Dlaczego wystarczy porównać każde spotkanie z poprzednim?

Po posortowaniu według czasu rozpoczęcia, jeśli dotąd nie wykryto żadnego konfliktu, dotychczasowe spotkania tworzą ciąg, w którym każde rozpoczyna się w chwili zakończenia poprzedniego lub później. Ostatnie spotkanie w tym ciągu kończy się najpóźniej. Nowe spotkanie, które rozpoczyna się w chwili jego zakończenia lub później, nie może nakładać się na żadne z wcześniejszych spotkań.

Czy spotkania, które tylko się stykają, nakładają się na siebie?

Nie w tym zadaniu: spotkanie może rozpocząć się dokładnie w chwili, gdy kończy się inne. Dlatego sprawdzenie ma postać ścisłej nierówności start < previous end. Gdyby spotkania stykające się w czasie były niedozwolone, sprawdzenie miałoby postać start ≤ previous end.

Jak znaleźć minimalną liczbę sal konferencyjnych?

Posortuj godziny rozpoczęcia i godziny zakończenia jako dwie oddzielne listy, a następnie przejdź przez obie: każde rozpoczęcie otwiera salę, a każde zakończenie, które następuje przed następnym rozpoczęciem lub w tej samej chwili, zwalnia jedną salę. Odpowiedzią jest największa liczba sal jednocześnie zajętych. Odpowiedź na pytanie tak lub nie jest tu równoznaczna z pytaniem, czy wystarczy jedna sala.

Python

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

Przypadki testowe

Przypadek 1

Przypadek 2

Wejście

starts = [9, 13, 10]
ends = [10, 15, 12]

Oczekiwane

true