Non-overlapping Intervals

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

La soluzione greedy ordina gli intervalli per fine in O(n log n) e poi li percorre una volta in O(n) , quindi il totale è O(n log n) . La copia ordinata degli intervalli occupa O(n) spazio. La versione con programmazione dinamica è O(n²) , mentre provare ogni insieme da mantenere è O(2^n) .

MedioIntervalli Greedy

+10

Ricevi un elenco di intervalli sotto forma di due array: l'intervallo i va da starts[i] a ends[i]. Rimuovi il minor numero possibile di intervalli, in modo che nessuno dei rimanenti si sovrapponga. Due intervalli che si toccano soltanto, quando uno termina esattamente nel punto in cui inizia l'altro, non si sovrappongono.

Scrivi una funzione chiamata eraseOverlapIntervals che restituisca il numero minimo di intervalli da rimuovere.

Funzione

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

startsinteger-array: l'inizio di ciascun intervallo
endsinteger-array: la 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 puoi mantenerne tre: [1,4] si sovrappone a [2,3] e [3,6] si sovrappone a [5,7], e qualsiasi gruppo di tre dei quattro contiene una di queste coppie.

Input: starts = [0, 0, 0]ends = [5, 5, 5]
Output: 2
Spiegazione: I tre intervalli sono tutti [0,5], quindi ognuno si sovrappone agli altri. Può rimanerne solo uno e rimuovi gli altri 2.

Input: starts = [4, 1, 2]ends = [6, 2, 4]
Output: 0
Spiegazione: [1,2], [2,4] e [4,6] si incontrano alla fine e all'inizio e non si sovrappongono mai, quindi non rimuovi nulla e la risposta è 0.

+17 test nascosti all’invio

Per approfondire

Supponiamo che ogni intervallo abbia anche un valore e che tu voglia ottenere il valore totale più alto tra gli intervalli che non si sovrappongono. Scegliere l’intervallo che termina per primo continua a funzionare? Cosa useresti invece?

Soluzione

Rimuovere il minor numero di intervalli equivale a mantenere il maggior numero di intervalli che non si sovrappongono, quindi la risposta è n meno quell'insieme più grande. Provare ogni insieme da mantenere richiede un tempo esponenziale, mentre la programmazione dinamica sulle catene di intervalli riduce il tempo a O(n²). Una regola greedy completa il lavoro in O(n log n): tra gli intervalli ancora compatibili, mantieni sempre quello che termina per primo.

Mantieni o rimuovi ogni intervallo

Corretto, ma non termina sui test più grandi

Intuizione

Riformula la domanda. Rimuovere il minor numero di intervalli significa mantenere il maggior numero di intervalli che non si sovrappongono, e la risposta è n meno quel numero. Cerca quindi il più grande insieme che puoi mantenere.

Ordina gli intervalli in base all’inizio e decidi per ciascuno, in quell’ordine, se rimuoverlo o mantenerlo. Puoi mantenerlo solo se inizia alla fine dell’ultimo intervallo mantenuto o dopo. Questo singolo controllo è sufficiente: gli intervalli mantenuti formano così una catena in cui ciascuno inizia alla fine di quello precedente o dopo, quindi non si sovrappongono tra loro. Prova entrambe le opzioni per ogni intervallo e scegli il risultato migliore.

Nel primo esempio, gli intervalli ordinati sono [1,4], [2,3], [3,6], [5,7]. Mantenere [1,4] blocca [2,3] e [3,6], che iniziano prima di 4, e lascia spazio per [5,7]: 2 mantenuti. Rimuovere [1,4] e mantenere [2,3] e poi [3,6] ne mantiene anch’esso 2. Nessun ramo arriva a 3, quindi rimuovi 4-2 = 2.

Ogni intervallo può raddoppiare il numero di rami, quindi n intervalli generano fino a 2^n percorsi. Già trenta intervalli che non si sovrappongono comportano più di un miliardo di chiamate, e i test arrivano fino a 5000 intervalli. Anche la ricorsione raggiunge una profondità di n livelli: 5000 chiamate nei test più grandi, oltre il limite predefinito di Python di 1,000.

Algoritmo

Ordina gli intervalli per inizio, mantenendo ogni inizio associato alla propria fine.
Definisci mostKept(i, last): il numero massimo di intervalli che puoi mantenere a partire dalla posizione i, quando last è la posizione dell’ultimo intervallo mantenuto (-1 se nessuno).
Superata la fine della lista, restituisci 0. Altrimenti, inizia da mostKept(i+1, last), il risultato della rimozione dell’intervallo i.
Se l’intervallo i inizia alla fine dell’intervallo last o dopo, prova anche 1 + mostKept(i+1, i) e mantieni il risultato 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 precedente risponde ancora e ancora alla stessa domanda: qual è la catena più lunga che termina con questo intervallo? Memorizza quella risposta una volta per intervallo. Ordina per punto iniziale e indica con chain[i] il maggior numero di intervalli che puoi mantenere quando l’intervallo i è l’ultimo mantenuto.

L’intervallo mantenuto subito prima di i deve terminare al punto iniziale di i o prima. Ogni intervallo di questo tipo viene prima nell’ordine ordinato: inizia prima di terminare, quindi inizia prima di starts[i]. Ne consegue che chain[i] = 1 + chain[j] per il miglior j precedente con ends[j] ≤ starts[i], oppure 1 quando nessun intervallo è compatibile. Il valore più grande in chain è il massimo numero di intervalli che puoi mantenere.

Nel primo esempio, ordinato come [1,4], [2,3], [3,6], [5,7], i valori sono 1, 1, 2 e 2: [3,6] può seguire [2,3] e [5,7] può seguire [1,4] o [2,3]. La catena più lunga è 2, quindi rimuovi 4-2 = 2.

Ogni intervallo esamina tutti gli intervalli che lo precedono: sono n(n-1)/2 controlli. Con n = 5000 sono circa 12,5 milioni di controlli: un numero gestibile in un linguaggio compilato, ma troppo lento nei linguaggi più lenti per i test più grandi, e molto meno efficiente dell’algoritmo greedy qui sotto.

Algoritmo

Ordina gli intervalli per punto iniziale, mantenendo ogni punto iniziale associato al proprio punto finale.
Imposta chain[i] = 1 per ogni intervallo.
Per ogni i e ogni j < i con ends[j] ≤ starts[i], imposta chain[i] a chain[j]+1 se è 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

Guarda l’intervallo con l’estremo finale più piccolo. Una soluzione ottimale lo mantiene sempre. Prendi un qualsiasi insieme più grande possibile di intervalli da mantenere e sostituisci il suo intervallo più anticipato con questo. Il nuovo intervallo termina non più tardi di quello che ha sostituito, quindi termina ancora all’inizio dell’intervallo successivo mantenuto o prima. L’insieme resta privo di sovrapposizioni e mantiene la stessa dimensione, quindi mantenere l’estremo finale più anticipato non ti costa nulla.

Una volta mantenuto, ogni intervallo che inizia prima del suo estremo finale si sovrappone a esso e deve essere rimosso. Quello che resta è la stessa domanda sugli intervalli che iniziano in corrispondenza di quell’estremo finale o dopo, quindi applica di nuovo la stessa regola. In pratica: ordina per estremo finale, percorri l’elenco e ricorda lastEnd, l’estremo finale dell’ultimo intervallo mantenuto. Mantieni un intervallo che inizia in corrispondenza di lastEnd o dopo; conta ogni altro intervallo come rimosso.

Il primo esempio, ordinato per estremo finale, è [2,3], [1,4], [3,6], [5,7]. Mantieni [2,3], quindi lastEnd = 3. [1,4] inizia a 1, prima di 3: rimuovilo. [3,6] inizia a 3, non prima di 3: mantienilo, lastEnd = 6. [5,7] inizia a 5, prima di 6: rimuovilo. Due rimossi.

Altri criteri sembrano allettanti, ma non funzionano. Ordinando per inizio, si mantiene [0,100] quando copre [1,2], [3,4] e [5,6], e si rimuovono tre intervalli invece di uno. Mantenere l’intervallo più corto non funziona con [1,5], [4,7], [6,10]: il breve [4,7] si sovrappone a entrambi gli altri, quindi mantenerlo comporta due rimozioni mentre ne basta una. L’estremo finale è il criterio che lascia più spazio a tutto ciò che viene dopo.

L’ordinamento richiede O(n log n) e la scansione O(n). La copia ordinata degli intervalli richiede O(n) spazio.

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 su 0.
Per ogni intervallo successivo, se inizia in corrispondenza o dopo lastEnd, 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

La maggior parte delle risposte sbagliate dipende dalla chiave di ordinamento o dal confronto nei punti di contatto.

Considerare gli intervalli che si toccano come sovrapposti. Con start > lastEnd invece di start ≥ lastEnd, la sequenza [1,2], [2,4], [4,6] perde [2,4], che inizia esattamente dove termina [1,2], e il risultato è 1 invece di 0.
Ordinare per inizio e mantenere sempre l’intervallo precedente in caso di sovrapposizione. Un intervallo ampio [0,100] fa quindi eliminare [1,2], [3,4] e [5,6]. Se ordini per inizio, tra i due intervalli sovrapposti mantieni quello che termina prima.
Confrontare ogni intervallo con quello adiacente nell’elenco ordinato anziché con l’ultimo intervallo mantenuto. Dopo aver rimosso [1,4], l’intervallo successivo deve essere confrontato con la fine di [2,3], non con 4.
Ordinare starts e ends come due elenchi separati. Ogni fine deve restare associata al proprio inizio, altrimenti confronti un inizio con la fine di un altro intervallo.
Restituire il numero di intervalli mantenuti. La domanda chiede il numero di intervalli rimossi, che è n meno quel numero.

Domande frequenti4

Qual è la complessità temporale degli intervalli non sovrapposti?

La soluzione greedy ordina gli intervalli per fine in O(n log n) e poi li percorre una volta in O(n), quindi il totale è O(n log n). La copia ordinata degli intervalli occupa O(n) spazio. La versione con programmazione dinamica è O(n²), mentre provare ogni insieme da mantenere è O(2^n).

Perché ordinare per orario di fine porta al minor numero di rimozioni?

L’intervallo che termina per primo può sostituire il primo intervallo di qualsiasi soluzione ottimale senza creare sovrapposizioni, perché termina non più tardi. Quindi esiste una soluzione ottimale che lo mantiene e, dopo aver rimosso tutto ciò che si sovrappone a esso, il problema rimanente è lo stesso su un insieme più piccolo. Ripetendo l’argomento, si dimostra che ogni scelta greedy è sicura.

Puoi invece ordinare in base all’ora di inizio?

Sì, con una regola diversa per le sovrapposizioni. Esamina gli intervalli in base all’inizio e, quando il successivo si sovrappone all’ultimo intervallo mantenuto, conta una rimozione e mantieni quello dei due che termina per primo. Rimuove lo stesso numero di intervalli dell’ordinamento per fine e richiede lo stesso tempo O(n log n).

Il problema degli intervalli non sovrapposti è uguale al problema della selezione delle attività?

È l'altro lato della stessa medaglia. La selezione delle attività richiede 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 i problemi.

Python

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

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

Non-overlapping Intervals

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Mantieni o rimuovi ogni intervallo

Catena più lunga con programmazione dinamica

Greedy: mantieni l’intervallo che termina per primo

Trappole e casi limite

Domande frequenti4

Problemi simili