Insert Interval

Q: Qual è la complessità temporale di Insert Interval?

La soluzione in un solo passaggio richiede un tempo O(n) , poiché ogni intervallo viene copiato o accorpato una sola volta, e usa O(n) spazio per un risultato di al massimo n+1 intervalli. Aggiungere l’intervallo e riordinare richiede O(n log n) .

Q: In che modo Insert Interval è diverso da Merge Intervals?

Unisci intervalli parte da un elenco non ordinato in cui qualsiasi intervallo può sovrapporsi a un altro, quindi prima lo ordina. Qui l’elenco è ordinato e i vecchi intervalli non si toccano mai, quindi solo il nuovo intervallo può innescare un’unione e gli intervalli con cui si unisce formano un’unica sequenza. È sufficiente un solo passaggio.

Q: Come si verifica se due intervalli si sovrappongono?

[a, b] e [c, d] condividono un punto esattamente quando a ≤ d e c ≤ b . In questo modo si considerano sovrapposti anche intervalli che si toccano, come [2, 4] e [4, 8] , come richiesto da questo problema. Per mantenere separati gli intervalli che si toccano, usa a < d e c < b .

MedioIntervalli

+10

Ricevi gli intervalli ordinati per punto iniziale in due array: l’intervallo i è [starts[i], ends[i]] e non ci sono due intervalli che si sovrappongono o si toccano. Inserisci il nuovo intervallo [newStart, newEnd], uniscilo a ogni intervallo con cui si sovrappone o che tocca e restituisci tutti gli intervalli come coppie [start, end] ordinate per punto iniziale.

Gli intervalli si toccano quando uno termina nel punto in cui inizia l’altro, come accade con [2, 4] e [4, 8], e gli intervalli che si toccano vengono uniti. [1, 2] e [3, 4] non hanno punti in comune, quindi restano separati.

Funzione

insertInterval(starts: integer-array, ends: integer-array, newStart: integer, newEnd: integer) → integer-2d-array

startsinteger-array: l'inizio di ciascun intervallo, in ordine crescente
endsinteger-array: la fine di ogni intervallo, le corrispondenze iniziano
newStartinteger: l'inizio dell'intervallo da inserire
newEndinteger: la fine dell'intervallo da inserire
Restituisceinteger-2d-array: gli intervalli dopo l'inserimento come coppie [inizio, fine], ordinate per inizio

Vincoli

1 ≤ starts.length == ends.length ≤ 2000
0 ≤ starts[i] ≤ ends[i] ≤ 10⁵
ends[i] < starts[i+1]: gli intervalli sono ordinati per inizio e non si sovrappongono né si toccano.
0 ≤ newStart ≤ newEnd ≤ 10⁵

Esempi

Input: starts = [1, 5, 10, 15]ends = [3, 7, 12, 18]newStart = 6newEnd = 11
Output: [[1, 3], [5, 12], [15, 18]]
Spiegazione: [6, 11] si sovrappone a [5, 7] e [10, 12], quindi i tre intervalli diventano [5, 12]. [1, 3] termina prima di 6 e [15, 18] inizia dopo 12, quindi entrambi rimangono invariati.

Input: starts = [2, 8]ends = [4, 9]newStart = 4newEnd = 8
Output: [[2, 9]]
Spiegazione: [4, 8] tocca [2, 4] in 4 e [8, 9] in 8, quindi tutti e tre si uniscono in [2, 9].

Input: starts = [1, 9]ends = [2, 10]newStart = 5newEnd = 6
Output: [[1, 2], [5, 6], [9, 10]]
Spiegazione: [5, 6] si trova nello spazio tra 2 e 9 e non tocca nessuno dei due vicini, quindi si inserisce tra loro e non si fonde nulla.

Per approfondire

Se inserisci molti intervalli uno dopo l’altro, come li memorizzeresti in modo che ogni inserimento costi O(log n) più un passaggio per ogni vecchio intervallo che ingloba?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

I vecchi intervalli sono ordinati e separati, quindi solo il nuovo intervallo può causare una fusione. Questo divide l’elenco in tre gruppi: intervalli che finiscono prima che inizi, intervalli che si sovrappongono o lo toccano e intervalli che iniziano dopo che è terminato. Copia il primo gruppo, fondi il gruppo centrale in un unico intervallo e copia l’ultimo. Una sola passata, senza ordinare.

Aggiungilo e unisci di nuovo tutto

Intuizione

Riutilizzo di Merge Intervals: aggiungi il nuovo intervallo, ordina tutti gli n+1 intervalli in base all'inizio e scorri la lista tenendo l'ultimo intervallo unito. Dopo l'ordinamento, un intervallo può sovrapporsi solo al gruppo che lo precede, quindi, quando l'inizio successivo è minore o uguale alla fine dell'intervallo tenuto, estendine la fine; altrimenti si apre uno spazio e inizia un nuovo intervallo.

L'ordinamento costa O(n log n) per correggere una lista che è fuori ordine in un punto, e ignora il fatto che i vecchi intervalli non si uniscono mai tra loro.

Algoritmo

Abbina ogni inizio alla sua fine e aggiungi [newStart, newEnd] all’elenco.
Ordina gli intervalli per inizio.
Percorrili in ordine, mantenendo l’ultimo intervallo unito.
Se il prossimo inizio è al massimo uguale alla fine mantenuta, porta la fine mantenuta al maggiore tra i due estremi.
Altrimenti aggiungi il prossimo intervallo come nuovo intervallo unito. Restituisci l’elenco unito.

def insertInterval(starts, ends, newStart, newEnd):
    intervals = list(zip(starts, ends))
    intervals.append((newStart, newEnd))
    intervals.sort()
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)  # overlaps or touches: stretch
        else:
            merged.append([start, end])  # a real gap: a new interval begins
    return merged

Un passaggio in tre parti

Intuizione

L’elenco è ordinato e i suoi intervalli sono separati, quindi quelli che incontrano il nuovo intervallo formano una sequenza continua. Tutto ciò che precede la sequenza ha ends[i] < newStart: termina prima che inizi il nuovo intervallo. Il confronto è stretto perché un intervallo che termina esattamente in newStart tocca il nuovo intervallo e deve essere unito.

All’interno della sequenza, un intervallo con starts[i] ≤ mergedEnd si sovrappone o tocca l’intervallo che stai costruendo, quindi lo estende fino all’inizio più piccolo e alla fine più grande. Il primo intervallo che inizia dopo mergedEnd conclude la sequenza, poiché tutti quelli successivi iniziano più a destra. Quando la sequenza è vuota, il nuovo intervallo viene inserito da solo. Nel primo esempio, [1, 3] viene copiato, [5, 7] e [10, 12] estendono [6, 11] fino a [5, 12], e [15, 18] viene copiato. Ogni intervallo viene esaminato una sola volta: tempo O(n) e nessuna memoria oltre a quella necessaria per il risultato.

Algoritmo

Copia gli intervalli nel risultato mentre ends[i] < newStart.
Imposta mergedStart = newStart e mergedEnd = newEnd.
Mentre starts[i] ≤ mergedEnd, imposta mergedStart all'inizio più piccolo e mergedEnd alla fine più grande, quindi prosegui.
Aggiungi [mergedStart, mergedEnd].
Copia gli intervalli rimanenti e restituisci il risultato.

def insertInterval(starts, ends, newStart, newEnd):
    n = len(starts)
    result = []
    i = 0
    # 1. Intervals that end before the new one starts stay as they are.
    while i < n and ends[i] < newStart:
        result.append([starts[i], ends[i]])
        i += 1
    # 2. Intervals that overlap or touch the new one fold into it.
    mergedStart, mergedEnd = newStart, newEnd
    while i < n and starts[i] <= mergedEnd:
        mergedStart = min(mergedStart, starts[i])
        mergedEnd = max(mergedEnd, ends[i])
        i += 1
    result.append([mergedStart, mergedEnd])
    # 3. Intervals that start after the merged one ends stay as they are.
    while i < n:
        result.append([starts[i], ends[i]])
        i += 1
    return result

Trappole e casi limite

Ineguaglianze errate per intervalli che si toccano. Con ends[i] ≤ newStart nel primo ciclo, oppure starts[i] < mergedEnd nel secondo, [2, 4] e [4, 8] rimangono separati. Il primo test è stretto, il secondo no.
Confrontare con mergedEnd + 1. Questo unisce [1, 2] e [3, 4], che non hanno punti in comune.
Mantenere newStart come inizio dell’intervallo unito. [6, 11] inizia all’interno di [5, 7], quindi il risultato inizia da 5.
Aggiungere il nuovo intervallo solo quando si sovrappone a qualcosa. Quando finisce in un intervallo vuoto o oltre uno dei due estremi, come accade con [5, 6], il ciclo centrale non viene eseguito, ma l’intervallo deve comunque essere aggiunto.
Leggere starts[i] prima di verificare i < n. Un nuovo intervallo che si estende oltre l’ultimo fa sì che l’indice superi la fine.

Domande frequenti3

Qual è la complessità temporale di Insert Interval?

La soluzione in un solo passaggio richiede un tempo O(n), poiché ogni intervallo viene copiato o accorpato una sola volta, e usa O(n) spazio per un risultato di al massimo n+1 intervalli. Aggiungere l’intervallo e riordinare richiede O(n log n).

In che modo Insert Interval è diverso da Merge Intervals?

Unisci intervalli parte da un elenco non ordinato in cui qualsiasi intervallo può sovrapporsi a un altro, quindi prima lo ordina. Qui l’elenco è ordinato e i vecchi intervalli non si toccano mai, quindi solo il nuovo intervallo può innescare un’unione e gli intervalli con cui si unisce formano un’unica sequenza. È sufficiente un solo passaggio.

Come si verifica se due intervalli si sovrappongono?

[a, b] e [c, d] condividono un punto esattamente quando a ≤ d e c ≤ b. In questo modo si considerano sovrapposti anche intervalli che si toccano, come [2, 4] e [4, 8], come richiesto da questo problema. Per mantenere separati gli intervalli che si toccano, usa a < d e c < b.

def insertInterval(starts, ends, newStart, newEnd):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

starts = [1, 5, 10, 15]
ends = [3, 7, 12, 18]
newStart = 6
newEnd = 11

Output atteso

[[1, 3], [5, 12], [15, 18]]