Insert Interval

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

La soluzione con una sola passata richiede un tempo O(n) : ogni intervallo viene copiato o accorpato esattamente una volta. Il risultato contiene fino a n+1 intervalli, quindi richiede O(n) spazio, e nient'altro cresce con l'input. Aggiungere l'intervallo e riordinare richiede invece O(n log n) .

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

Merge Intervals parte da un elenco non ordinato in cui un intervallo qualsiasi può sovrapporsi a un altro, quindi prima deve ordinare l’elenco. In Insert Interval l’elenco è già ordinato e i vecchi intervalli non si toccano mai, quindi solo il nuovo intervallo può innescare un’unione. Gli intervalli con cui si unisce formano un’unica sequenza ininterrotta, ed è per questo che basta un solo passaggio senza ordinare.

Q: Come si verifica se due intervalli si sovrappongono?

Gli intervalli [a, b] e [c, d] condividono almeno un punto esattamente quando a ≤ d e c ≤ b . In questo modo si considerano sovrapposti anche gli intervalli che si toccano, come [2, 4] e [4, 8] , ed è ciò che richiede questo problema. Se gli intervalli che si toccano dovessero rimanere separati, useresti invece a < d e c < b .

Q: La ricerca binaria può rendere più veloce l'inserimento di un intervallo?

La ricerca binaria trova dove inizia e finisce l’intervallo unito in O(log n) , perché gli inizi e le fini sono entrambi ordinati. La funzione restituisce comunque una nuova lista e copiare al suo interno gli intervalli non modificati costa O(n) . Quindi il totale rimane O(n) . La ricerca binaria conviene quando gli intervalli si trovano in una struttura che può rimuovere e inserire un intervallo senza copiarlo, come un albero bilanciato.

MedioIntervalli

+10

Ricevi un elenco di intervalli ordinati per valore iniziale, fornito come due array della stessa lunghezza: l'intervallo i è [starts[i], ends[i]]. Nessuno di essi si sovrappone o tocca gli altri. Ricevi anche un nuovo intervallo, [newStart, newEnd]. Inseriscilo, uniscilo a ogni intervallo con cui si sovrappone o che tocca e restituisci tutti gli intervalli come array 2D di coppie [start, end], ordinati per valore iniziale.

Due intervalli si toccano quando uno termina dove inizia l'altro, come accade con [2, 4] e [4, 8], e gli intervalli che si toccano si fondono in uno solo. [1, 2] e [3, 4] non condividono alcun punto, quindi restano separati.

Funzione

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

startsinteger-array: l'inizio di ogni intervallo, in ordine crescente
endsinteger-array: la fine di ogni intervallo, in corrispondenza degli inizi
newStartinteger: l'inizio dell'intervallo da inserire
newEndinteger: la fine dell'intervallo da inserire
Restituisceinteger-2d-array: gli intervalli dopo l’inserimento come coppie [start, end], ordinate per start

Vincoli

1 ≤ starts.length == ends.length ≤ 2000
0 ≤ starts[i] ≤ ends[i] ≤ 10⁵
ends[i] < starts[i+1]: gli intervalli sono ordinati per punto di inizio e nessuna coppia si sovrappone o si tocca.
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. Il contatto conta come sovrapposizione, 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 elementi vicini, quindi si inserisce tra di loro e non si unisce a niente.

+20 test nascosti all’invio

Per approfondire

Supponiamo che tu inserisca molti nuovi intervalli, uno dopo l’altro, nella stessa lista. Come memorizzeresti gli intervalli 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 già separati e in ordine, quindi solo il nuovo intervallo può causare una fusione. Questo divide la lista in tre gruppi: intervalli che terminano prima che inizi quello nuovo, intervalli che si sovrappongono o lo toccano e intervalli che iniziano dopo che termina. Copia il primo gruppo, fondi il gruppo centrale in un unico intervallo, copia l’ultimo gruppo. Una sola passata, senza ordinare.

Aggiungilo e unisci di nuovo tutto

Intuizione

Se hai risolto Merge Intervals, puoi riutilizzare la soluzione qui. Inserisci il nuovo intervallo nella lista, ordina tutti gli n+1 intervalli in base all'inizio e uniscili. Dopo l'ordinamento, un intervallo può sovrapporsi solo al gruppo immediatamente precedente, quindi percorri la lista tenendo l'ultimo intervallo unito. Quando l'inizio successivo è minore o uguale alla sua fine, estendi la fine. Altrimenti c'è un vero intervallo vuoto e inizia un nuovo intervallo.

Esegui l'algoritmo sul primo esempio. La lista diventa [1, 3], [5, 7], [6, 11], [10, 12], [15, 18]. [1, 3] resta da solo, perché 5 è maggiore di 3. 6 è minore o uguale a 7, quindi [5, 7] si estende a [5, 11]. 10 è minore o uguale a 11, quindi si estende a [5, 12]. 15 è maggiore di 12, quindi [15, 18] inizia un nuovo intervallo.

È corretto e, con 2000 intervalli, viene eseguito rapidamente. Tuttavia, ignora due fatti che ti sono stati dati: la lista è già ordinata e i vecchi intervalli non si uniscono mai tra loro. Pagare O(n log n) per riordinare una lista che è fuori ordine in un solo punto è il passaggio che un intervistatore ti chiederà di eliminare.

Algoritmo

Abbina ogni inizio alla sua fine e aggiungi [newStart, newEnd] all’elenco.
Ordina gli intervalli in base all’inizio.
Percorrili in ordine, mantenendo l’ultimo intervallo unito.
Se l’inizio successivo è minore o uguale alla fine dell’intervallo mantenuto, porta la fine mantenuta al maggiore tra i due estremi.
Altrimenti aggiungi l’intervallo successivo come nuovo intervallo unito. Restituisci l’elenco degli intervalli uniti.

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

Percorri l’elenco una volta con un indice i e dividilo in tre gruppi. Per prima cosa, ogni intervallo con ends[i] < newStart finisce prima che inizi il nuovo, quindi non ha punti in comune con esso: copialo nel risultato. Il test usa un < stretto perché un intervallo che termina esattamente in newStart tocca il nuovo intervallo e deve essere unito.

In secondo luogo, ogni intervallo con starts[i] ≤ mergedEnd si sovrappone all’intervallo che stai costruendo o lo tocca. Accorpalo: mergedStart diventa l’inizio più piccolo e mergedEnd la fine più grande. Gli intervalli di questo gruppo sono consecutivi, perché l’elenco è ordinato. Quando un intervallo inizia dopo mergedEnd, tutti quelli successivi iniziano ancora più a destra, quindi nessun intervallo dopo di esso può essere unito. Aggiungi l’intervallo unito; questo passaggio gestisce anche il caso in cui il gruppo sia vuoto e il nuovo intervallo venga inserito da solo.

In terzo luogo, copia tutto ciò che resta. Questi intervalli iniziano dopo la fine dell’intervallo unito e sono già separati tra loro.

Segui il primo esempio. [1, 3] termina prima di 6: copialo. [5, 7] inizia a 5, che è minore o uguale a 11: l’intervallo unito diventa [5, 11]. [10, 12] inizia a 10, minore o uguale a 11: diventa [5, 12]. [15, 18] inizia dopo 12, quindi aggiungi [5, 12] e copia [15, 18]. Ogni intervallo viene esaminato una volta, quindi il tempo è O(n) e l’unica memoria aggiuntiva è quella del risultato stesso.

Algoritmo

Copia gli intervalli nel risultato finché ends[i] < newStart.
Imposta mergedStart = newStart e mergedEnd = newEnd.
Finché starts[i] ≤ mergedEnd, imposta mergedStart sull'inizio più piccolo e mergedEnd sulla fine più grande, quindi vai avanti.
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

Il ciclo è breve, quindi la maggior parte dei bug deriva da un confronto errato o da un caso dimenticato alle estremità dell’elenco.

Usare la disuguaglianza sbagliata per gli intervalli che si toccano. Con ends[i] ≤ newStart nel primo ciclo, o starts[i] < mergedEnd nel secondo, [2, 4] e [4, 8] restano separati. Gli intervalli che si toccano si uniscono, quindi il primo test è stretto e il secondo no.
Unire intervalli che sembrano solo adiacenti. [1, 2] e [3, 4] non hanno punti in comune, quindi confrontare con mergedEnd + 1 unisce intervalli che dovrebbero restare separati.
Mantenere newStart come inizio dell’intervallo unito. Quando il nuovo intervallo inizia all’interno di uno vecchio, come [6, 11] all’interno di [5, 7], il risultato inizia da 5. Prendi il minore dei due inizi.
Aggiungere il nuovo intervallo solo quando si sovrappone a qualcosa. Quando si trova prima di tutti gli intervalli, dopo tutti gli intervalli o in uno spazio vuoto, il ciclo centrale non viene mai eseguito e il nuovo intervallo deve comunque essere aggiunto.
Leggere starts[i] o ends[i] prima di controllare i < n. Quando il nuovo intervallo va oltre l’ultimo intervallo, l’indice supera la fine degli array.

Domande frequenti4

Qual è la complessità temporale di Insert Interval?

La soluzione con una sola passata richiede un tempo O(n): ogni intervallo viene copiato o accorpato esattamente una volta. Il risultato contiene fino a n+1 intervalli, quindi richiede O(n) spazio, e nient'altro cresce con l'input. Aggiungere l'intervallo e riordinare richiede invece O(n log n).

In che cosa Insert Interval è diverso da Merge Intervals?

Merge Intervals parte da un elenco non ordinato in cui un intervallo qualsiasi può sovrapporsi a un altro, quindi prima deve ordinare l’elenco. In Insert Interval l’elenco è già ordinato e i vecchi intervalli non si toccano mai, quindi solo il nuovo intervallo può innescare un’unione. Gli intervalli con cui si unisce formano un’unica sequenza ininterrotta, ed è per questo che basta un solo passaggio senza ordinare.

Come si verifica se due intervalli si sovrappongono?

Gli intervalli [a, b] e [c, d] condividono almeno un punto esattamente quando a ≤ d e c ≤ b. In questo modo si considerano sovrapposti anche gli intervalli che si toccano, come [2, 4] e [4, 8], ed è ciò che richiede questo problema. Se gli intervalli che si toccano dovessero rimanere separati, useresti invece a < d e c < b.

La ricerca binaria può rendere più veloce l'inserimento di un intervallo?

La ricerca binaria trova dove inizia e finisce l’intervallo unito in O(log n), perché gli inizi e le fini sono entrambi ordinati. La funzione restituisce comunque una nuova lista e copiare al suo interno gli intervalli non modificati costa O(n). Quindi il totale rimane O(n). La ricerca binaria conviene quando gli intervalli si trovano in una struttura che può rimuovere e inserire un intervallo senza copiarlo, come un albero bilanciato.

Python

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

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

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