Rimozioni minime per evitare sovrapposizioni
Pianificare mantenendo gli intervalli con fine più anticipata
Rimozioni minime per evitare sovrapposizioni è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
L'obiettivo delle rimozioni
Ha a disposizione intervalli sovrapposti e desidera il minor numero possibile di rimozioni affinché non si sovrappongano più. Ne mantenga quanti più possibile. ✂️
Invertire il problema
Rimuovere il minor numero possibile equivale a mantenere il maggior numero di intervalli non sovrapposti. Risolva il problema del mantenimento: le rimozioni saranno n meno il numero di intervalli mantenuti.
Questo è il problema della selezione delle attività
Mantenere il maggior numero di intervalli non sovrapposti equivale al classico problema della selezione delle attività. La stessa idea greedy risolve entrambi i problemi.
Ordinare per fine
In questo caso l'ordine vincente è quello per tempo di fine, non per inizio. Terminare presto libera la sequenza temporale il prima possibile per il successivo intervallo che si potrebbe mantenere.
intervals.sort(key=lambda x: x[1])La scelta greedy
Mantenga sempre l'intervallo che termina prima tra quelli ancora compatibili. In questo modo lascia il massimo spazio per gli altri.
Tenere traccia dell'ultima fine mantenuta
Conservi la fine dell'ultimo intervallo mantenuto. L'intervallo successivo è compatibile solo se il suo inizio è uguale o successivo a quella frontiera.
if start >= last_end:
last_end = endContare le rimozioni
Quando un intervallo inizia prima di last_end, è in conflitto: lo elimini e aumenti di uno il conteggio delle rimozioni. Altrimenti lo mantenga.
else:
removed += 1Perché vince la fine più vicina
Lo dimostra un argomento di scambio: sostituire un intervallo mantenuto con quello compatibile che termina prima non riduce mai il numero di intervalli che si possono mantenere.
Gestire il caso limite del contatto
Decida se [1, 2] e [2, 3] debbano essere considerati sovrapposti. Se è consentito condividere solo un estremo, utilizzi start >= last_end come test.
L'algoritmo greedy completo
Ordini per fine, esegua una sola scansione e conti i conflitti. Il costo totale è O(n log n) per l'ordinamento più un'unica scansione lineare.
removed = 0; last_end = float('-inf')
for s, e in intervals:
if s >= last_end: last_end = e
else: removed += 1Una struttura familiare
Questo schema consente di programmare il maggior numero di riunioni in una sala o di eseguire il maggior numero di lavori su una macchina. Lo riconosca ogni volta che è necessario minimizzare i conflitti.
Verifica rapida
Si mantengono greedy gli intervalli non sovrapposti.
Riepilogo
Il numero minimo di rimozioni equivale a n meno il numero massimo di intervalli che si possono mantenere. Ordini per fine, mantenga greedy gli intervalli compatibili che terminano prima e conti quelli rimanenti. 🚀
Domande Frequenti
La lezione «Rimozioni minime per evitare sovrapposizioni» è gratuita?
Sì — il testo completo di «Rimozioni minime per evitare sovrapposizioni» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Rimozioni minime per evitare sovrapposizioni»?
Pianificare mantenendo gli intervalli con fine più anticipata Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Rimozioni minime per evitare sovrapposizioni»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Ordinare gli intervalli per inizio
- Unire gli intervalli sovrapposti
- Line sweep per la sovrapposizione massima
- Rimozioni minime per evitare sovrapposizioni