Merge Intervals

Q: Qual è la complessità temporale di Merge Intervals?

La soluzione con ordinamento e scansione richiede un tempo O(n log n) per n intervalli: l'ordinamento ha un costo O(n log n) e la scansione O(n). Usa O(n) di spazio aggiuntivo per le coppie ordinate e il risultato.

Q: Perché ordinare gli intervalli in base all'inizio e non alla fine?

Ordinati per inizio, gli intervalli possono sovrapporsi solo al gruppo che stai costruendo, quindi basta un confronto con la fine di quel gruppo per decidere tutto. Ordinati per fine, un intervallo successivo può iniziare prima dei gruppi che hai già chiuso: [5, 6] viene prima di [1, 10] e una scansione in avanti manterrebbe erroneamente 5 come inizio.

Q: Riesci a unire gli intervalli senza spazio aggiuntivo?

Sì, se puoi modificare l’input. Ordina gli intervalli sul posto, poi scrivi ogni intervallo unito all’inizio dello stesso array e tieni traccia dell’indice dell’ultimo intervallo scritto. Il tempo rimane O(n log n) e l’unico spazio aggiuntivo è quello usato dall’ordinamento del tuo linguaggio.

MedioIntervalli Ordinamento

+10

Ricevi un insieme di intervalli, ciascuno un intervallo di numeri interi da un inizio a una fine. Unisci ogni gruppo di intervalli sovrapposti in un unico intervallo che copra l’intero gruppo e restituisci gli intervalli uniti ordinati per inizio. Gli intervalli che si toccano soltanto, come [1, 4] e [4, 5], si considerano sovrapposti.

Gli intervalli sono forniti in due array della stessa lunghezza: l’intervallo i è [starts[i], ends[i]]. Restituisci un array 2D, una lista di coppie [start, end].

Funzione

mergeIntervals(starts: integer-array, ends: integer-array) → integer-2d-array

startsinteger-array: l'inizio di ogni intervallo
endsinteger-array: la fine di ogni intervallo, allo stesso indice del suo inizio
Restituisceinteger-2d-array: gli intervalli uniti come coppie [start, end], ordinate per valore iniziale

Vincoli

1 ≤ starts.length == ends.length ≤ 10⁴
0 ≤ starts[i] ≤ ends[i] ≤ 10⁴
Gli intervalli arrivano in qualsiasi ordine.
Gli intervalli che si toccano solo a un estremo si considerano sovrapposti.

Esempi

Input: starts = [5, 1, 12, 3]ends = [7, 4, 14, 6]
Output: [[1, 7], [12, 14]]
Spiegazione: In ordine di inizio, [1, 4] si sovrappone a [3, 6], che si sovrappone a [5, 7], quindi i tre diventano [1, 7]. [12, 14] inizia dopo 7 e rimane da solo.

Per approfondire

Gli intervalli arrivano già uniti e ordinati in base al punto iniziale, e devi aggiungere un nuovo intervallo. Riesci a restituire l’elenco unito in tempo O(n), senza ordinare di nuovo?

Soluzione

Unire le coppie in qualsiasi ordine richiede passaggi ripetuti, perché ogni unione allarga un intervallo e gli permette di raggiungere intervalli che hai già controllato. Ordina invece per inizio. Così un intervallo può sovrapporsi solo al gruppo che stai costruendo e un solo passaggio è sufficiente.

Unisci le coppie sovrapposte finché non cambia più nulla

Corretto, ma non termina sui test più grandi

Intuizione

Gli intervalli [a, b] e [c, d] si sovrappongono quando c ≤ b e a ≤ d, e [min(a, c), max(b, d)] li comprende entrambi. Ogni fusione rimuove un intervallo, quindi il processo termina e, quando un passaggio completo non trova sovrapposizioni, non ci sono due intervalli rimasti che condividano un punto. Un solo passaggio non basta: un intervallo fuso è più ampio e ora può raggiungere un intervallo con cui la sua parte più piccola era stata confrontata in precedenza durante il passaggio.

Un passaggio confronta circa n²/2 coppie e potrebbero servire fino a n passaggi: O(n³). Un solo passaggio su 10^4 intervalli richiede già 5 × 10^7 confronti.

Algoritmo

Copia starts e ends e tieni un conteggio n degli intervalli attivi.
Confronta ogni intervallo i con tutti gli intervalli successivi j. Se si sovrappongono, estendi i in modo da coprire j, sposta l’ultimo intervallo attivo nello slot j e diminuisci n di uno.
Dopo una fusione, controlla di nuovo lo slot j, perché ora contiene un intervallo diverso.
Ripeti i passaggi finché uno di essi non effettua alcuna fusione.
Abbina ogni inizio attivo alla sua fine, ordina le coppie in base all’inizio e restituiscile.

def mergeIntervals(starts, ends):
    s = list(starts)
    e = list(ends)
    n = len(s)
    changed = True
    while changed:
        changed = False
        i = 0
        while i < n:
            j = i + 1
            while j < n:
                if s[j] <= e[i] and s[i] <= e[j]:
                    # Intervals i and j overlap: interval i absorbs interval j.
                    s[i] = min(s[i], s[j])
                    e[i] = max(e[i], e[j])
                    # Move the last interval into slot j and drop the last slot.
                    n -= 1
                    s[j] = s[n]
                    e[j] = e[n]
                    changed = True
                else:
                    j += 1
            i += 1
    return sorted([s[k], e[k]] for k in range(n))

Ordina per inizio e scorri una sola volta

Intuizione

Dopo aver ordinato per inizio, l'intervallo successivo inizia non prima di qualsiasi intervallo dell'ultimo gruppo, che termina in e. Se il suo inizio è al massimo e, si sovrappone al gruppo o lo tocca e vi si aggiunge, mentre e diventa il maggiore dei due estremi. Se il suo inizio è maggiore di e, neanche gli intervalli successivi possono raggiungere il gruppo, perché iniziano più a destra. Il gruppo è completo e l'intervallo ne apre uno nuovo.

L'ordinamento costa O(n log n) e la scansione visita ogni intervallo una volta. I gruppi si chiudono da sinistra a destra, quindi il risultato è ordinato per inizio.

Algoritmo

Abbina ogni inizio alla sua fine: l’intervallo i è [starts[i], ends[i]].
Ordina le coppie in base all’inizio.
Esamina le coppie ordinate. Se il risultato è vuoto oppure la coppia inizia dopo la fine dell’ultimo intervallo unito, aggiungi la coppia come nuovo intervallo.
Altrimenti imposta la fine dell’ultimo intervallo unito sul valore maggiore tra la sua fine e la fine della coppia.
Restituisci l’elenco degli intervalli uniti.

def mergeIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            if end > merged[-1][1]:
                merged[-1][1] = end
        else:
            merged.append([start, end])
    return merged

Trappole e casi limite

Confrontare con < invece che con ≤. Intervalli contigui come [1, 4] e [4, 5] devono essere uniti.
Impostare la fine all'estremo finale del nuovo intervallo invece che al maggiore dei due. [1, 10] seguito da [2, 3] deve rimanere [1, 10].
Ordinare starts da solo e poi leggere ends nelle nuove posizioni, facendo sì che un inizio venga associato alla fine di un altro intervallo. Associali prima a coppie oppure ordina gli indici.
Confrontare con l'intervallo di input precedente invece che con l'ultimo intervallo unito. In [1, 10], [2, 3], [4, 5], il terzo intervallo è contenuto in [1, 10], anche se non tocca [2, 3].
In C, non impostare *returnSize al numero di intervalli uniti e la dimensione di ogni colonna a 2.

Domande frequenti3

Qual è la complessità temporale di Merge Intervals?

La soluzione con ordinamento e scansione richiede un tempo O(n log n) per n intervalli: l'ordinamento ha un costo O(n log n) e la scansione O(n). Usa O(n) di spazio aggiuntivo per le coppie ordinate e il risultato.

Perché ordinare gli intervalli in base all'inizio e non alla fine?

Ordinati per inizio, gli intervalli possono sovrapporsi solo al gruppo che stai costruendo, quindi basta un confronto con la fine di quel gruppo per decidere tutto. Ordinati per fine, un intervallo successivo può iniziare prima dei gruppi che hai già chiuso: [5, 6] viene prima di [1, 10] e una scansione in avanti manterrebbe erroneamente 5 come inizio.

Riesci a unire gli intervalli senza spazio aggiuntivo?

Sì, se puoi modificare l’input. Ordina gli intervalli sul posto, poi scrivi ogni intervallo unito all’inizio dello stesso array e tieni traccia dell’indice dell’ultimo intervallo scritto. Il tempo rimane O(n log n) e l’unico spazio aggiuntivo è quello usato dall’ordinamento del tuo linguaggio.

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

Test #1

Test #2

Argomenti

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

Output atteso

[[1, 7], [12, 14]]