Meeting Rooms

Q: Qual è la complessità temporale di Meeting Rooms?

Ordinare le riunioni in base all'ora di inizio costa O(n log n) , e la scansione che confronta gli elementi vicini è O(n) , quindi il costo totale è O(n log n) . Confrontare invece ogni coppia costa O(n²) .

Q: Perché è sufficiente confrontare ogni riunione con quella precedente?

Dopo aver ordinato per orario di inizio, se finora non è stata rilevata alcuna sovrapposizione, gli incontri considerati finora formano una catena in cui ciascuno inizia all’ora di fine del precedente o successivamente. L’ultimo della catena termina più tardi. Un nuovo incontro che inizia all’ora della sua fine o successivamente non può sovrapporsi ad alcuno degli incontri precedenti.

Q: Le riunioni che si toccano si considerano sovrapposte?

Non in questo problema: una riunione può iniziare nel momento esatto in cui ne finisce un’altra. Ecco perché il controllo è un start < previous end stretto. Se le riunioni che si toccano fossero vietate, il controllo diventerebbe start ≤ previous end .

Q: Come si trova il numero minimo di sale riunioni?

Ordina gli orari di inizio e quelli di fine in due elenchi separati, poi scorri entrambi: ogni inizio apre una sala e ogni fine che arriva prima o allo stesso tempo del prossimo inizio ne libera una. Il numero massimo di sale aperte contemporaneamente è la risposta. Rispondere qui alla domanda sì o no equivale a chiedersi se basta una sola sala.

FacileIntervalli Ordinamento

+10

Ricevi un elenco di riunioni sotto forma di due array: la riunione i si svolge da starts[i] a ends[i]. Una persona vuole partecipare a tutte, quindi nessuna coppia di riunioni può sovrapporsi. Una riunione può iniziare esattamente nel momento in cui ne termina un'altra. Restituisci true se la persona può partecipare a tutte le riunioni e false altrimenti.

Funzione

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

startsinteger-array: l'orario di inizio di ogni riunione
endsinteger-array: l'ora di fine di ogni riunione, allo stesso indice del relativo inizio
Restituisceboolean: true se nessuna coppia di riunioni si sovrappone, false altrimenti

Vincoli

1 ≤ starts.length == ends.length ≤ 5000
0 ≤ starts[i] < ends[i] ≤ 10⁶
Le riunioni non sono ordinate. Due riunioni possono essere identiche.

Esempi

Input: starts = [9, 13, 10]ends = [10, 15, 12]
Output: true
Spiegazione: In ordine cronologico, le riunioni si svolgono dalle 9 alle 10, dalle 10 alle 12 e dalle 13 alle 15. La seconda inizia nel momento in cui termina la prima, il che è consentito, quindi la risposta è true.

Input: starts = [1, 4, 7]ends = [5, 6, 8]
Output: false
Spiegazione: La riunione dalle 1 alle 5 è ancora in corso alle 4, quando inizia la riunione dalle 4 alle 6, quindi la risposta è false.

+15 test nascosti all’invio

Per approfondire

Se le riunioni vengono prenotate una alla volta, come controlleresti ogni nuova prenotazione confrontandola con l’orario in O(log n), senza ordinare di nuovo tutto?

Soluzione

Controllare ogni coppia di riunioni individua qualsiasi sovrapposizione, ma ha un costo di O(n²). Ordinare per orario di inizio cambia la domanda: a quel punto una riunione può sovrapporsi solo a quella successiva nell’ordine ordinato, quindi basta un confronto per riunione.

Confronta ogni coppia

Corretto, ma non termina sui test più grandi

Intuizione

Due riunioni si sovrappongono quando ciascuna inizia prima che l’altra finisca. Per le riunioni da 1 a 5 e da 4 a 6: 1 è prima di 6 e 4 è prima di 5, quindi si sovrappongono. Per le riunioni da 9 a 10 e da 10 a 12: 10 non è prima di 10, quindi si toccano soltanto.

Usare < stretto su entrambi i lati permette a una riunione di iniziare esattamente quando un’altra finisce. Esegui il test su ogni coppia e restituisci false al primo conflitto.

Il problema è il numero di coppie. Con n = 5000 riunioni ci sono circa 12,5 milioni di coppie e, se non ci sono sovrapposizioni nella pianificazione, devi controllarle tutte: è troppo lento per i test più grandi.

Algoritmo

Per ogni indice i e ogni indice j successivo:
Se starts[i] < ends[j] e starts[j] < ends[i], le due riunioni si sovrappongono: restituisci false.
Se nessuna coppia si sovrappone, restituisci 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

Ordina per inizio e controlla gli elementi adiacenti

Intuizione

Ordina le riunioni per orario di inizio, mantenendo ogni inizio associato alla propria fine. Ora considera una qualsiasi riunione e quella immediatamente precedente. Se quella precedente termina dopo l’inizio di quella successiva, si sovrappongono. Altrimenti, la riunione successiva inizia nel momento in cui termina quella precedente o più tardi.

Perché basta controllare solo la riunione vicina? Se ogni riunione esaminata finora inizia nel momento in cui termina quella precedente o più tardi, le riunioni esaminate finora non si sovrappongono mai e quella immediatamente precedente è quella che termina più tardi. Una nuova riunione che inizia nel momento in cui termina o più tardi inizia nel momento in cui terminano tutte le altre o più tardi.

Nel primo esempio, le riunioni ordinate sono dalle 9 alle 10, dalle 10 alle 12 e dalle 13 alle 15. L’inizio alle 10 non è precedente alla fine alle 10 e l’inizio alle 13 non è precedente alla fine alle 12, quindi non c’è sovrapposizione. Gli orari di inizio uguali causano sempre una sovrapposizione, perché ogni riunione dura almeno un’unità, e anche in questo caso il controllo le rileva.

L’ordinamento ha un costo di O(n log n) e la scansione è O(n). La copia delle riunioni mantenendo le coppie richiede O(n) di spazio.

Algoritmo

Abbina ogni inizio alla relativa fine.
Ordina le coppie in base all’ora di inizio.
Per ogni riunione dopo la prima, confronta il suo inizio con la fine della riunione precedente.
Se l’inizio è minore, restituisci false.
Dopo il ciclo, restituisci 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

Trappole e casi limite

Gli errori più comuni riguardano quali estremi vengono confrontati e come vengono trattate le riunioni che si toccano.

Ordinare starts e lasciare ends nell'ordine di input. Ogni orario di fine deve rimanere associato al proprio orario di inizio, altrimenti confronti un orario di inizio con l'orario di fine di un'altra riunione.
Usare ≤ invece di <. Le riunioni dalle 9 alle 10 e dalle 10 alle 12 si toccano ma non si sovrappongono, e la risposta per queste riunioni è true.
Verificare soltanto che ogni riunione termini prima che inizi la successiva, seguendo l'ordine di input. L'input non è ordinato, quindi le riunioni adiacenti nell'input non dicono nulla.
Scrivere il test per la coppia con una sola condizione, come starts[j] < ends[i]. Funziona solo quando la riunione j inizia più tardi; per le riunioni dalle 5 alle 6 e dalle 0 alle 1, in quest'ordine, 0 < 6 segnala un conflitto che non c'è.

Domande frequenti4

Qual è la complessità temporale di Meeting Rooms?

Ordinare le riunioni in base all'ora di inizio costa O(n log n), e la scansione che confronta gli elementi vicini è O(n), quindi il costo totale è O(n log n). Confrontare invece ogni coppia costa O(n²).

Perché è sufficiente confrontare ogni riunione con quella precedente?

Dopo aver ordinato per orario di inizio, se finora non è stata rilevata alcuna sovrapposizione, gli incontri considerati finora formano una catena in cui ciascuno inizia all’ora di fine del precedente o successivamente. L’ultimo della catena termina più tardi. Un nuovo incontro che inizia all’ora della sua fine o successivamente non può sovrapporsi ad alcuno degli incontri precedenti.

Le riunioni che si toccano si considerano sovrapposte?

Non in questo problema: una riunione può iniziare nel momento esatto in cui ne finisce un’altra. Ecco perché il controllo è un start < previous end stretto. Se le riunioni che si toccano fossero vietate, il controllo diventerebbe start ≤ previous end.

Come si trova il numero minimo di sale riunioni?

Ordina gli orari di inizio e quelli di fine in due elenchi separati, poi scorri entrambi: ogni inizio apre una sala e ogni fine che arriva prima o allo stesso tempo del prossimo inizio ne libera una. Il numero massimo di sale aperte contemporaneamente è la risposta. Rispondere qui alla domanda sì o no equivale a chiedersi se basta una sola sala.

Python

def canAttendMeetings(starts, ends):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

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

Atteso

true