Non-overlapping Intervals

Q: Qual è la complessità temporale degli intervalli non sovrapposti?

La soluzione greedy ordina in base alla fine in O(n log n) e scorre gli intervalli una volta, quindi la complessità totale è O(n log n) , con spazio O(n) per la copia ordinata. La versione con programmazione dinamica è O(n²) , mentre provare ogni insieme da mantenere richiede O(2^n) .

MedioIntervalli Greedy

+10

L’intervallo i va da starts[i] a ends[i]. Restituisci il numero minimo di intervalli da rimuovere affinché nessuno dei rimanenti si sovrapponga. Due intervalli che si toccano soltanto, in cui uno termina esattamente nel punto in cui inizia l’altro, non si sovrappongono.

Funzione

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

startsinteger-array: l'inizio di ogni intervallo
endsinteger-array: alla fine di ogni intervallo, allo stesso indice del suo inizio
Restituisceinteger: il minor numero di intervalli da rimuovere affinché i restanti non si sovrappongano

Vincoli

1 ≤ starts.length == ends.length ≤ 5000
-5 × 10⁴ ≤ starts[i] < ends[i] ≤ 5 × 10⁴
Gli intervalli non sono ordinati. Due intervalli possono essere identici.

Esempi

Input: starts = [3, 1, 5, 2]ends = [6, 4, 7, 3]
Output: 2
Spiegazione: In ordine di inizio, gli intervalli sono [1,4], [2,3], [3,6] e [5,7]. Mantieni [2,3] e [3,6], che si toccano soltanto, e rimuovi gli altri 2. Non è possibile mantenerne tre: [1,4] si sovrappone a [2,3] e [3,6] si sovrappone a [5,7].

Input: starts = [0, 0, 0]ends = [5, 5, 5]
Output: 2
Spiegazione: Tutti e tre gli intervalli sono [0,5], quindi ogni coppia si sovrappone. Uno rimane e rimuovi 2.

Input: starts = [4, 1, 2]ends = [6, 2, 4]
Output: 0
Spiegazione: [1,2], [2,4] e [4,6] si incontrano in corrispondenza degli estremi e non si sovrappongono mai, quindi non rimuovi nulla e la risposta è 0.

Per approfondire

Supponiamo che ogni intervallo abbia un valore e che tu voglia ottenere il valore totale più alto tra gli intervalli che non si sovrappongono. Continuare a scegliere l’intervallo che termina per primo funziona ancora?

Soluzione

Rimuovere il minor numero di intervalli equivale a mantenere il maggior numero di intervalli che non si sovrappongono: la risposta è n meno quel conteggio. Una regola greedy trova il conteggio in O(n log n): tra gli intervalli che possono ancora essere mantenuti, scegli sempre quello che termina per primo.

Mantieni o rimuovi ciascun intervallo

Corretto, ma non termina sui test più grandi

Intuizione

Ordina gli intervalli in base all'inizio e decidi per ciascuno se mantenerlo o rimuoverlo. Puoi mantenerlo solo se inizia alla fine dell'ultimo intervallo mantenuto o dopo, così gli intervalli mantenuti formano una catena senza sovrapposizioni. Prova entrambe le scelte per ogni intervallo e prendi il conteggio maggiore; la risposta è n meno questo valore.

Ogni intervallo può raddoppiare i rami, quindi n intervalli portano fino a 2^n percorsi. Trenta intervalli che non si sovrappongono significano già oltre un miliardo di chiamate, e n arriva fino a 5000.

Algoritmo

Ordina gli intervalli in base all'inizio, mantenendo ogni inizio insieme alla propria fine.
Definisci mostKept(i, last): il numero massimo di intervalli che puoi mantenere a partire dalla posizione i, quando last è l'ultimo intervallo mantenuto (-1 se nessuno).
Superata la fine, restituisci 0. Altrimenti considera mostKept(i+1, last), che rimuove l'intervallo i.
Se l'intervallo i inizia in corrispondenza o dopo la fine di last, prova anche 1 + mostKept(i+1, i) e mantieni il valore maggiore.
Restituisci n meno mostKept(0, -1).

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)

    def most_kept(i, last):
        # The most intervals you can keep among i..n-1, when interval last
        # is the latest one kept so far (-1: nothing kept yet).
        if i == n:
            return 0
        best = most_kept(i + 1, last)  # remove interval i
        if last == -1 or intervals[i][0] >= intervals[last][1]:
            best = max(best, 1 + most_kept(i + 1, i))  # keep interval i
        return best

    return n - most_kept(0, -1)

Catena più lunga con programmazione dinamica

Corretto, ma non termina sui test più grandi

Intuizione

La ricerca continua a porre la stessa domanda: quanto è lunga la catena più lunga che termina con questo intervallo? Rispondi una volta per intervallo. Ordina per inizio e lascia che chain[i] rappresenti il numero massimo di intervalli che puoi mantenere con l’intervallo i come ultimo.

Un intervallo che può venire subito prima di i termina in corrispondenza o prima di starts[i], quindi inizia prima e si trova prima nell’ordine ordinato. Questo dà chain[i] = 1 + chain[j] per il migliore j di questo tipo, oppure 1 se non ce n’è nessuno compatibile. Nel primo esempio i valori sono 1, 1, 2 e 2, quindi mantieni 2 intervalli e ne rimuovi 2.

Il doppio ciclo esegue n(n-1)/2 controlli: circa 12,5 milioni quando n = 5000.

Algoritmo

Ordina gli intervalli per orario di inizio, mantenendo ogni orario di inizio associato al proprio orario di fine.
Imposta chain[i] = 1 per ogni intervallo.
Per ogni i e ogni j < i con ends[j] ≤ starts[i], imposta chain[i] su chain[j]+1 quando è maggiore.
Restituisci n meno il valore più grande in chain.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)
    # chain[i]: the most intervals you can keep when interval i is the last one kept
    chain = [1] * n
    for i in range(n):
        for j in range(i):
            if intervals[j][1] <= intervals[i][0] and chain[j] + 1 > chain[i]:
                chain[i] = chain[j] + 1
    return n - max(chain)

Greedy: mantieni l’intervallo che termina per primo

Intuizione

Prendi l’intervallo con l’estremo finale più piccolo. Esiste una soluzione ottimale che lo mantiene: in qualsiasi insieme più grande possibile, puoi sostituire il primo intervallo con questo. Il suo estremo finale non è più avanti, quindi è ancora minore o uguale all’inizio del successivo intervallo mantenuto, e l’insieme conserva la stessa dimensione senza sovrapposizioni. Ogni intervallo che inizia prima del suo estremo finale si sovrappone a esso e deve essere rimosso; ciò che resta è lo stesso problema sugli intervalli che iniziano in corrispondenza o dopo quell’estremo finale.

Nel primo esempio, ordinando per estremo finale, mantieni [2,3], rimuovi [1,4], mantieni [3,6] e rimuovi [5,7]. Mantenere invece l’intervallo più corto non funziona con [1,5], [4,7], [6,10]: [4,7] si sovrappone a entrambi gli altri e comporta due rimozioni, mentre ne basta una.

L’ordinamento costa O(n log n) e la scansione O(n).

Algoritmo

Ordina gli intervalli in base alla fine, mantenendo ogni fine associata al proprio inizio.
Mantieni il primo intervallo: imposta lastEnd sulla sua fine e removed a 0.
Per ogni intervallo successivo, se inizia a lastEnd o dopo, mantienilo e imposta lastEnd sulla sua fine.
Altrimenti aggiungi 1 a removed.
Restituisci removed.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(ends, starts))  # by end time
    removed = 0
    last_end = intervals[0][0]  # the interval that ends first is always kept
    for end, start in intervals[1:]:
        if start >= last_end:
            last_end = end  # it fits after the last kept interval: keep it
        else:
            removed += 1  # it overlaps the last kept interval: remove it
    return removed

Trappole e casi limite

Considerare sovrapposti gli intervalli che si toccano. Con start > lastEnd invece di start ≥ lastEnd, la catena [1,2], [2,4], [4,6] dà 1 invece di 0.
Ordinare per inizio e mantenere l’intervallo precedente in caso di sovrapposizione. Un intervallo ampio [0,100] fa poi scartare [1,2], [3,4] e [5,6]: tre rimozioni invece di una.
Confrontare ogni intervallo con quello vicino nell’elenco ordinato invece che con l’ultimo intervallo mantenuto. Nel primo esempio, [3,6] deve essere confrontato con la fine di [2,3], non con quella dell’intervallo rimosso [1,4], altrimenti il risultato è 3.
Ordinare starts e ends come due elenchi separati. Ogni fine deve rimanere associata al proprio inizio.
Restituire il numero di intervalli mantenuti invece di quello degli intervalli rimossi.

Domande frequenti3

Qual è la complessità temporale degli intervalli non sovrapposti?

La soluzione greedy ordina in base alla fine in O(n log n) e scorre gli intervalli una volta, quindi la complessità totale è O(n log n), con spazio O(n) per la copia ordinata. La versione con programmazione dinamica è O(n²), mentre provare ogni insieme da mantenere richiede O(2^n).

Puoi ordinare invece per ora di inizio?

Sì, con una regola diversa per le sovrapposizioni. Scorri gli intervalli in base all'inizio e, quando il successivo si sovrappone all'ultimo intervallo mantenuto, conta una rimozione e conserva quello dei due che termina prima. Restituisce lo stesso conteggio nello stesso tempo O(n log n).

Gli intervalli non sovrapposti sono la stessa cosa del problema della selezione delle attività?

È l'altro lato del problema. La selezione delle attività cerca il maggior numero di intervalli che non si sovrappongono; questo problema chiede di rimuoverne il minor numero possibile, cioè n meno quel numero. La stessa regola greedy, mantenere l'attività che termina per prima, risolve entrambi.

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

Test #1

Test #2

Test #3

Argomenti

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

Output atteso

Non-overlapping Intervals

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Mantieni o rimuovi ciascun intervallo

Catena più lunga con programmazione dinamica

Greedy: mantieni l’intervallo che termina per primo

Trappole e casi limite

Domande frequenti3

Problemi simili