Ostatnio zadano mi to pytanie w wywiadzie. Mimo że byłem w stanie wymyślićO(n²) rozwiązanie, ankieter miał obsesję na punkcieO(n) rozwiązanie. Sprawdziłem też kilka innych rozwiązańO(n logn) które zrozumiałem, aleO(n) rozwiązaniem nadal nie jest moja filiżanka herbaty, która zakłada spotkania posortowane według czasu rozpoczęcia.

Czy ktoś może to wyjaśnić?

Oświadczenie o problemie: Dostanieszn spotkania. Każde spotkanie zawiera godzinę rozpoczęcia i godzinę zakończenia. Musisz skutecznie odwrócić wszystkie sprzeczne terminy.

Osoba: 1,2, 3, 4, 5
App Start: 2, 4, 29, 10, 22
Koniec aplikacji: 5, 7, 34, 11, 36

Odpowiedź: 2x1 5x3

O(n logn) algorytm: oddzielny punkt początkowy i końcowy w ten sposób:

2s, 4s, 29s, 10s, 22s, 5e, 7e, 34e, 11e, 36e

następnie posortuj wszystkie te punkty (dla uproszczenia załóżmy, że każdy punkt jest unikalny):

2s, 4s, 5e, 7e, 10s, 11e, 22s, 29s, 34e, 36e

jeśli mamy kolejne starty bez końca, to nakładają się na siebie: 2s, 4s przylegają do siebie, więc nakładają się na siebie

Będziemy zachowywać liczbę „s” i za każdym razem, gdy napotkamy, będzie +1, a gdy napotkamy e, zmniejszamy liczbę o 1.