Unire gli intervalli sovrapposti
Combinare gli intervalli adiacenti o sovrapposti
Unire gli intervalli sovrapposti è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 2 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 Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
L'obiettivo dell'unione
Data una serie di intervalli, desidera unire quelli adiacenti o sovrapposti per ottenere il minor numero possibile di intervalli non sovrapposti. 🧩
Quando due intervalli si sovrappongono
Due intervalli si sovrappongono quando uno inizia prima che l'altro termini. Dopo averli ordinati per inizio, ciò significa che il prossimo inizio è minore o uguale alla fine corrente.
Ordinare prima, sempre
L'unione funziona da sinistra a destra solo se gli intervalli sono ordinati, quindi inizi ordinandoli per inizio. Questa è la base dell'intera scansione.
intervals.sort(key=lambda x: x[0])Mantenere un intervallo corrente
Scorra la lista ordinata mantenendo un unico intervallo unito corrente. Ogni nuovo intervallo lo estende oppure avvia un nuovo intervallo.
Estendere in caso di sovrapposizione
Se il prossimo inizio rientra nell'intervallo corrente, i due intervalli si sovrappongono, quindi estenda la fine corrente scegliendo la maggiore delle due fini.
cur_end = max(cur_end, end)Scegliere la fine massima
Utilizzi sempre max per calcolare la nuova fine. Un intervallo breve contenuto in uno più lungo non deve restringere l'intervallo già costruito.
Chiudere e aprirne uno nuovo
Se il prossimo inizio supera la fine corrente, c'è un vuoto. Aggiunga l'intervallo completato alla risposta e inizi un nuovo intervallo corrente.
result.append([cur_start, cur_end])Non dimenticare l'ultimo
Il ciclo costruisce l'intervallo finale, ma non lo aggiunge mai. Al termine del ciclo, esegua append con l'ultimo intervallo corrente, così non andrà perso.
Il contatto conta come sovrapposizione
Decida se [1, 3] e [3, 5] debbano essere uniti. Di solito sì, quindi utilizzi start <= cur_end. Legga il problema per confermare questa regola sui casi limite.
La scansione completa
Una sola scansione dopo l'ordinamento fornisce tutti gli intervalli uniti, quindi il metodo completo richiede O(n log n) per l'ordinamento più una scansione lineare.
for s, e in intervals[1:]:
if s <= cur_end:
cur_end = max(cur_end, e)
else:
result.append([cur_start, cur_end]); cur_start, cur_end = s, eUn uso comune
La fusione è alla base dei calendari e dei sistemi di prenotazione: unisca i periodi occupati per vedere il tempo realmente libero. Molti problemi delle gare di programmazione nascondono questa stessa struttura.
Verifica rapida
Si uniscono gli intervalli dopo averli ordinati per inizio.
Riepilogo
Ordini per inizio, mantenga un intervallo corrente e lo estenda usando max in caso di sovrapposizione, oppure lo aggiunga e lo reimposti quando c'è un intervallo vuoto. Ricordi l'aggiunta finale. 🚀
Domande Frequenti
La lezione «Unire gli intervalli sovrapposti» è gratuita?
Sì — il testo completo di «Unire gli intervalli sovrapposti» è 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 Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Unire gli intervalli sovrapposti»?
Combinare gli intervalli adiacenti o sovrapposti Eserciti Competitive Programming Academy 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 Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Unire gli intervalli sovrapposti»?
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 Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy 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