Meeting Rooms II

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

Entrambe le soluzioni veloci hanno complessità O(n log n) . La versione con heap ordina le riunioni ed esegue un’operazione sull’heap di O(log n) per ogni riunione; la versione con due liste esegue due ordinamenti e una scansione di O(n) . Entrambe usano spazio aggiuntivo di O(n) . Contare le riunioni in corso a ogni inizio ha complessità O(n²) .

MedioIntervalli Heap Ordinamento

+10

Ricevi un elenco di riunioni sotto forma di due array: la riunione i si svolge da starts[i] a ends[i]. Una stanza può ospitare una sola riunione alla volta e una riunione può iniziare in una stanza esattamente nel momento in cui termina un'altra riunione che vi si svolge.

Scrivi una funzione chiamata minMeetingRooms che restituisca il numero minimo di stanze in cui possono svolgersi tutte le riunioni.

Funzione

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

startsinteger-array: l'ora di inizio di ogni riunione
endsinteger-array: l'ora di fine di ogni riunione, allo stesso indice del suo inizio
Restituisceinteger: il minor numero di sale in grado di ospitare tutte le riunioni

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 = [4, 1, 7, 2]ends = [8, 5, 9, 6]
Output: 3
Spiegazione: Al tempo 4, le riunioni dalle 1 alle 5, dalle 2 alle 6 e dalle 4 alle 8 sono tutte in corso, quindi ti servono almeno 3 sale. Tre sono sufficienti: la riunione dalle 7 alle 9 occupa la sala che si libera alle 5.

Input: starts = [0, 2, 3]ends = [10, 3, 5]
Output: 2
Spiegazione: La riunione da 0 a 10 tiene occupata una sala per tutto il tempo. La riunione da 2 a 3 ha bisogno di una seconda sala e quella da 3 a 5 occupa la stessa sala appena si libera, quindi bastano 2 sale.

+17 test nascosti all’invio

Per approfondire

Puoi anche indicare in quale stanza si svolge ciascuna riunione, utilizzando al massimo il numero di stanze indicato nella risposta?

Soluzione

Il numero di stanze di cui hai bisogno è il numero massimo di riunioni in corso nello stesso momento. Contare le riunioni in corso a ogni orario di inizio permette di trovarlo in O(n²). L'ordinamento trasforma la domanda in un'unica scansione della giornata: un min-heap degli orari in cui le stanze si liberano, oppure due elenchi ordinati di orari di inizio e fine, dà la risposta in O(n log n).

Conta le riunioni in corso a ogni ora di inizio

Corretto, ma non termina sui test più grandi

Intuizione

In ogni momento, ogni riunione in corso ha bisogno di una sala tutta per sé. Quindi servono almeno tante sale quante sono le riunioni in corso contemporaneamente nel momento di massima affluenza. Quel numero è anche sufficiente: assegna le sale in ordine di orario di inizio e una nuova sala viene aperta solo quando tutte le sale sono occupate, il che significa che in quel momento è in corso quel numero di riunioni.

Il numero di riunioni in corso aumenta solo quando ne inizia una, quindi il momento di massima affluenza coincide con l'inizio di una riunione. Per ogni riunione i, conta le riunioni j con starts[j] ≤ starts[i] < ends[j]: sono iniziate e non sono ancora terminate. Una riunione che termina esattamente a starts[i] non viene conteggiata, perché in quel momento la sua sala torna a essere libera.

Nel primo esempio, al tempo 4 sono in corso le riunioni dalle 1 alle 5, dalle 2 alle 6 e dalle 4 alle 8: 3. Al tempo 7 sono in corso solo quelle dalle 4 alle 8 e dalle 7 alle 9: 2. Il conteggio massimo è 3.

Ognuna delle n riunioni esamina tutte le n riunioni. Con n = 5000, si tratta di 25 milioni di controlli: una frazione di secondo in C, diversi secondi in Python o R e quattro volte tanto ogni volta che n raddoppia.

Algoritmo

Per ogni riunione i, imposta running a 0.
Per ogni riunione j, aggiungi 1 a running quando starts[j] ≤ starts[i] < ends[j].
Conserva il valore più grande di running che hai visto.
Restituisci quel valore più grande.

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-heap degli orari in cui le stanze si liberano

Intuizione

Assegna le sale come farebbe una persona alla reception. Esamina le riunioni in ordine di orario di inizio. Per ciascuna, guarda la sala che si libera per prima. Se è libera quando inizia la riunione, assegna quella sala alla riunione. Altrimenti, tutte le sale sono ancora occupate, quindi ne apri una nuova.

È sicuro controllare solo quella sala. Se la sala che si libera per prima è ancora occupata, lo sono tutte. Se è libera, una qualsiasi sala libera vale quanto un’altra: le riunioni successive iniziano a quest’ora o più tardi, quindi tutte le sale che sono libere adesso resteranno libere per tutte.

Ti serve l’orario di liberazione più vicino tra le sale, e questo cambia dopo ogni riunione. Un min-heap memorizza un orario di fine per ogni sala e ti restituisce il più piccolo. Riutilizzare una sala sostituisce il suo orario di fine con quello della nuova riunione; aprire una sala aggiunge un nuovo orario di fine. Nel primo esempio, ordinate per orario di inizio: da 1 a 5 dà [5], da 2 a 6 dà [5, 6], da 4 a 8 dà [5, 6, 8] e da 7 a 9 trova 5 uguale o precedente a 7 e lo sostituisce, lasciando [6, 8, 9]. Tre sale.

L’ordinamento ha un costo di O(n log n) e ogni riunione richiede un’operazione sull’heap di O(log n). heapq di Python, PriorityQueue di Java, priority_queue di C++ con greater, BinaryHeap di Rust con Reverse, container/heap di Go e SplMinHeap di PHP ti forniscono l’heap. Negli altri linguaggi lo mantieni in un array: il padre dell’indice i si trova in (i-1)/2 e un valore risale finché è più piccolo del proprio padre.

Algoritmo

Ordina le riunioni per orario di inizio, mantenendo ogni orario di inizio associato al proprio orario di fine.
Per ogni riunione, se l'heap non è vuoto e il suo orario di fine più vicino è uguale o precedente all'orario di inizio della riunione, sostituisci quell'orario di fine con l'orario di fine della riunione.
Altrimenti inserisci l'orario di fine della riunione: si apre una nuova sala.
Restituisci la dimensione dell'heap, con una voce per ogni sala.

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)

Ordina separatamente gli inizi e le fini

Intuizione

L'heap ricorda a quale stanza appartiene ciascun orario di fine, ma la risposta è solo un conteggio. Quando inizia una riunione, conta solo sapere se una riunione è già terminata e ha lasciato una stanza libera; non importa quale riunione fosse. Quindi ordina gli inizi e le fini in due elenchi separati e scorri gli inizi, usando un puntatore ended nell'elenco delle fini.

Per ogni inizio, nell'ordine: se è uguale o successivo a endTimes[ended], una riunione è terminata entro quel momento. La sua stanza accoglie la nuova riunione e ended avanza. Altrimenti, tutte le stanze in uso sono ancora occupate e rooms aumenta di uno. Ogni inizio utilizza al massimo una fine, proprio come una stanza riutilizzata nell'heap sostituisce una vecchia fine con una nuova.

Nel primo esempio gli inizi sono 1, 2, 4, 7 e le fini 5, 6, 8, 9. Gli inizi 1, 2 e 4 precedono tutti la fine 5, quindi rooms sale a 3. L'inizio 7 è uguale o successivo a 5, quindi riutilizza quella stanza e ended avanza alla fine 6. La risposta è 3. Il simbolo ≥ è ciò che permette a riunioni consecutive di condividere una stanza: nel secondo esempio, l'inizio 12 coincide con la fine 12 e riutilizza la stanza.

Il conteggio non supera mai il picco effettivo: quando rooms aumenta, la fine successiva è ancora nel futuro, quindi in quel momento sono in corso tutte le rooms riunioni. Raggiunge anche il picco, perché un inizio evita di aprire una stanza solo quando una fine effettiva, al suo stesso orario o precedente, ne ha liberata una. Due ordinamenti costano O(n log n), lo scorrimento O(n) e le copie ordinate richiedono O(n) spazio.

Algoritmo

Ordina una copia degli orari di inizio e una copia degli orari di fine.
Imposta rooms e ended su 0.
Per ogni orario di inizio, in ordine, se è uguale o successivo a endTimes[ended], aggiungi 1 a ended: la riunione occupa una sala liberata.
Altrimenti aggiungi 1 a rooms.
Restituisci 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

Trappole e casi limite

La maggior parte dei bug riguarda il confronto nel momento in cui due riunioni si toccano oppure la sala che viene controllata.

Controllare start > end invece di start ≥ end. Così, una riunione non può usare una sala nel momento in cui si libera e le riunioni dalle 10 alle 12, dalle 12 alle 14 e dalle 14 alle 16 richiedono 2 sale invece di 1.
Controllare l’ultima sala che hai aperto invece di quella che si libera per prima. Per le riunioni dall’1 alle 3, dalle 2 alle 10 e dalle 4 alle 6, l’ultima sala aperta è occupata fino alle 10, quindi ne apri una terza, mentre la prima è libera dalle 3.
Prendere il numero massimo di riunioni che si sovrappongono a una riunione, più uno. La riunione dalle 0 alle 10 si sovrappone alle riunioni dalle 2 alle 3 e dalle 3 alle 5, ma queste due non si sovrappongono tra loro, quindi bastano 2 sale, non 3.
Confondere i due approcci con ordinamento. L’heap richiede che ogni orario di fine resti abbinato al proprio orario di inizio prima di ordinare per orario di inizio; l’approccio con due liste ordina intenzionalmente gli orari di inizio e quelli di fine separatamente.

Domande frequenti4

Qual è la complessità temporale di Meeting Rooms II?

Entrambe le soluzioni veloci hanno complessità O(n log n). La versione con heap ordina le riunioni ed esegue un’operazione sull’heap di O(log n) per ogni riunione; la versione con due liste esegue due ordinamenti e una scansione di O(n). Entrambe usano spazio aggiuntivo di O(n). Contare le riunioni in corso a ogni inizio ha complessità O(n²).

Perché un min-heap risolve Meeting Rooms II?

Considerando le riunioni in ordine di inizio, l’unica sala che vale la pena controllare è quella che si libera per prima. Un min-heap degli orari di fine ti permette di ottenere quella sala in O(1) e di aggiornare la struttura in O(log n). L’heap cresce solo quando tutte le sale sono occupate, quindi la sua dimensione finale corrisponde al numero minimo di sale necessario.

È possibile risolvere Meeting Rooms II senza un heap?

Sì. Ordina gli orari di inizio e quelli di fine in due liste separate e scorri gli inizi con un puntatore negli orari di fine. Un inizio allo stesso orario o dopo il prossimo orario di fine non ancora utilizzato riutilizza una sala; qualsiasi altro inizio ne apre una. La stessa idea funziona come linea di scansione: trasforma ogni riunione in un evento +1 all'inizio e in un evento -1 alla fine, elabora le fini prima degli inizi quando gli orari coincidono e tieni traccia del totale progressivo massimo.

La risposta è uguale al numero massimo di riunioni che si sovrappongono contemporaneamente?

Sì. Le riunioni che si svolgono nello stesso momento hanno bisogno di stanze diverse, quindi te ne servono almeno altrettante. Assegnando a ogni riunione, in ordine di inizio, una stanza qualsiasi che sia libera, non te ne serviranno mai di più: perciò il numero massimo di riunioni sovrapposte è esattamente la risposta.

Python

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

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

Meeting Rooms II

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Conta le riunioni in corso a ogni ora di inizio

Min-heap degli orari in cui le stanze si liberano

Ordina separatamente gli inizi e le fini

Trappole e casi limite

Domande frequenti4

Problemi simili