0Pricing
Coding Interview Prep · Lezione

Pianificazione e fusione degli intervalli

Risolva i problemi meeting-rooms e non-overlapping-intervals ordinando per tempo di fine, e fonda gli intervalli nel problema merge-intervals ordinando per tempo di inizio.

Pianificazione e fusione degli intervalli è una lezione Coding Interview Prep 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 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.

Panoramica dei problemi di intervalli

I problemi di intervalli compaiono continuamente nei colloqui tecnici su pianificazione, gestione dei calendari e allocazione delle risorse. Gli schemi principali sono: unire gli intervalli sovrapposti, contare il numero minimo di sale riunioni, trovare il massimo insieme di intervalli non sovrapposti e inserire un nuovo intervallo. La maggior parte dei problemi di intervalli inizia con lo stesso passaggio: ordinare gli intervalli per orario di inizio, oppure per orario di fine, a seconda del problema. Scegliere correttamente la chiave di ordinamento è spesso la parte più difficile.

# Intervals: each = [start, end] (inclusive or exclusive by problem)
# Example:
intervals = [[1,3],[2,6],[8,10],[15,18]]
# Sorted by start (already sorted here)
# Visually:
# [1,3]    |-|
# [2,6]      |---|
# [8,10]             |--|
# [15,18]                    |---|
print('Intervals ready for analysis')

Unire gli intervalli sovrapposti

Merge Intervals (LeetCode 56): data una lista di intervalli, unisca tutti quelli sovrapposti. Algoritmo: ordini gli intervalli per orario di inizio. Scorra la lista ordinata; se l'intervallo corrente si sovrappone all'ultimo intervallo unito, cioè se il suo inizio ≤ la fine dell'ultimo intervallo unito, estenda la fine dell'ultimo intervallo unito al massimo tra le due estremità. In caso contrario, aggiunga l'intervallo corrente come nuovo intervallo unito. Tempo: O(n log n) per l'ordinamento, O(n) per la fusione.

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])  # sort by start
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        last_end = merged[-1][1]
        if start <= last_end:
            # Overlapping: extend the last interval
            merged[-1][1] = max(last_end, end)
        else:
            # Non-overlapping: add as new interval
            merged.append([start, end])
    return merged

print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]
print(merge_intervals([[1,4],[4,5]]))
# [[1,5]] (touching intervals merge)

Inserire un intervallo

Insert Interval (LeetCode 57): data una lista ordinata e non sovrapposta, inserisca un nuovo intervallo e proceda nuovamente alla fusione. Scorra la lista in tre fasi: (1) aggiunga tutti gli intervalli che terminano prima dell'inizio del nuovo intervallo; (2) unisca tutti gli intervalli che si sovrappongono al nuovo intervallo, estendendone i limiti; (3) aggiunga tutti gli intervalli rimanenti. Si tratta di un'unica scansione O(n) dopo l'ordinamento O(n log n), già eseguito in questo problema.

def insert_interval(intervals, new_interval):
    result = []
    i = 0
    n = len(intervals)
    # Phase 1: intervals before new_interval
    while i < n and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1
    # Phase 2: merge overlapping intervals
    while i < n and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1
    result.append(new_interval)
    # Phase 3: remaining intervals
    while i < n:
        result.append(intervals[i])
        i += 1
    return result

print(insert_interval([[1,3],[6,9]], [2,5]))  # [[1,5],[6,9]]
print(insert_interval([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]))
# [[1,2],[3,10],[12,16]]

Meeting Rooms I: è possibile partecipare a tutte le riunioni?

Meeting Rooms I (LeetCode 252): dati gli intervalli temporali delle riunioni, determini se una persona può partecipare a tutte. Ordini gli intervalli per orario di inizio; se una riunione inizia prima della fine di quella precedente, le due riunioni si sovrappongono. Questo è il controllo più semplice sugli intervalli: O(n log n) complessivo. L'idea fondamentale è che, dopo l'ordinamento, sia sufficiente confrontare le coppie consecutive.

def can_attend_meetings(intervals):
    intervals.sort(key=lambda x: x[0])
    for i in range(1, len(intervals)):
        # Current meeting starts before previous ends?
        if intervals[i][0] < intervals[i-1][1]:
            return False
    return True

print(can_attend_meetings([[0,30],[5,10],[15,20]]))  # False (0,30 overlaps 5,10)
print(can_attend_meetings([[7,10],[2,4]]))           # True (4 < 7, no overlap)

Meeting Rooms II: numero minimo di sale

Meeting Rooms II (LeetCode 253): trovi il numero minimo di sale conferenze necessarie per svolgere contemporaneamente tutte le riunioni. Usi un min-heap per tenere traccia della sala che si libera prima. Ordini le riunioni per orario di inizio. Per ogni nuova riunione: se inizia dopo l'orario di fine della sala che si libera prima, riutilizzi quella sala, eseguendo pop e push. In caso contrario, apra una nuova sala. La dimensione dell'heap alla fine corrisponde al numero di sale necessarie.

import heapq

def min_meeting_rooms(intervals):
    if not intervals: return 0
    intervals.sort(key=lambda x: x[0])  # sort by start
    heap = []  # min-heap of end times
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)  # reuse earliest-ending room
        else:
            heapq.heappush(heap, end)     # open a new room
    return len(heap)

print(min_meeting_rooms([[0,30],[5,10],[15,20]]))  # 2
print(min_meeting_rooms([[7,10],[2,4]]))           # 1
print(min_meeting_rooms([[9,10],[4,9],[4,17]]))    # 2

Alternativa della sweep line per contare le sale

Un approccio alternativo O(n log n) è la sweep line. Crei eventi per ogni inizio di intervallo (+1) e per ogni fine (-1). Ordini tutti gli eventi per orario, mettendo la fine prima dell'inizio in caso di parità se desidera estremi non inclusivi. Scorra gli eventi da sinistra a destra, mantenendo un conteggio progressivo delle riunioni attive. Il conteggio massimo è il numero minimo di sale necessarie. Questo approccio è più intuitivo per alcune persone e si generalizza ad altri problemi di conteggio sugli intervalli.

def min_rooms_sweep(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))   # meeting starts
        events.append((end, -1))    # meeting ends
    # Sort: same time → end (-1) before start (1) if exclusive
    events.sort(key=lambda x: (x[0], x[1]))
    max_rooms = current = 0
    for _, delta in events:
        current += delta
        max_rooms = max(max_rooms, current)
    return max_rooms

print(min_rooms_sweep([[0,30],[5,10],[15,20]]))  # 2
print(min_rooms_sweep([[1,5],[2,6],[3,7]]))       # 3 (all overlap at t=3)

Intervalli non sovrapposti: selezione massima

Non-Overlapping Intervals (LeetCode 435): trovi il numero minimo di intervalli da rimuovere affinché quelli rimanenti non si sovrappongano. Questo equivale a trovare il numero massimo di intervalli non sovrapposti, cioè il problema della selezione delle attività, e a restituire come rimozioni gli intervalli rimanenti. Ordini gli intervalli per orario di fine: mantenga greedy l'intervallo che termina prima, perché massimizza lo spazio disponibile per gli intervalli successivi. Quando l'intervallo seguente si sovrappone, lo scarti e incrementi il conteggio delle rimozioni.

def erase_overlap_intervals(intervals):
    if not intervals: return 0
    intervals.sort(key=lambda x: x[1])  # sort by END time
    removals = 0
    last_end = float('-inf')
    for start, end in intervals:
        if start >= last_end:
            last_end = end  # keep this interval
        else:
            removals += 1   # remove this interval (it overlaps)
    return removals

print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]]))  # 1 (remove [1,3])
print(erase_overlap_intervals([[1,2],[1,2],[1,2]]))        # 2
print(erase_overlap_intervals([[1,2],[2,3]]))              # 0 (no overlap)

Perché ordinare per l'ora di fine e non per quella di inizio

Per la selezione delle attività (insieme massimo di attività non sovrapposte), ordinare per ora di fine è dimostrabilmente ottimale. L'intuizione è semplice: un'attività che termina presto lascia più spazio alle attività successive. Se ordiniamo per ora di inizio, potremmo scegliere un'attività molto lunga che inizia presto e blocca molte attività successive più brevi. Argomento dello scambio: se la soluzione ottimale sceglie l'attività A invece di G, che termina per prima, sostituiamo A con G: G non termina più tardi, quindi non entra in conflitto con alcuna attività con cui A non fosse già in conflitto.

# Counterexample for sorting by START time:
# [[1,10],[2,3],[4,5]] — sorted by start: [1,10],[2,3],[4,5]
# Sort-by-start greedy keeps [1,10], can't add [2,3] or [4,5] (all overlap [1,10])
# Selects: 1 interval

# Sort-by-end greedy:
# [[2,3],[4,5],[1,10]] — sorted by end
# Keep [2,3] (end=3), then [4,5] (start=4 >= 3, keep), then [1,10] (start=1 < 5, skip)
# Selects: 2 intervals — OPTIMAL

intervals = [[1,10],[2,3],[4,5]]
intervals.sort(key=lambda x: x[1])
last_end = float('-inf')
count = 0
for s, e in intervals:
    if s >= last_end:
        count += 1; last_end = e
print('Max non-overlapping:', count)  # 2

Intersezioni tra liste di intervalli

Interval List Intersections (LeetCode 986): trovare tutte le coppie che si intersecano a partire da due liste di intervalli ordinate. Si utilizzi un approccio a due puntatori. A ogni passaggio, si calcola l'intersezione della coppia corrente (il massimo degli inizi e il minimo delle fini). Se l'inizio ≤ la fine, l'intersezione è valida. Poi si avanza il puntatore dell'intervallo che termina per primo. Complessità temporale O(m+n).

def interval_intersection(A, B):
    result = []
    i = j = 0
    while i < len(A) and j < len(B):
        # Intersection boundaries
        lo = max(A[i][0], B[j][0])
        hi = min(A[i][1], B[j][1])
        if lo <= hi:
            result.append([lo, hi])  # valid intersection
        # Advance pointer of interval that ends first
        if A[i][1] < B[j][1]:
            i += 1
        else:
            j += 1
    return result

A = [[0,2],[5,10],[13,23],[24,25]]
B = [[1,5],[8,12],[15,24],[25,26]]
print(interval_intersection(A, B))
# [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Partizionamento delle etichette

Partition Labels (LeetCode 763): suddividere una stringa nel maggior numero possibile di parti, in modo che ogni carattere compaia in al più una parte. Strategia greedy: per ogni carattere, si individua la sua ultima occorrenza. Si percorre la stringa mantenendo un max_end. Quando i == max_end, la partizione corrente è completa: se ne registra la lunghezza e si inizia una nuova partizione. In apparenza, questo è un problema di fusione di intervalli.

def partition_labels(s):
    last = {c: i for i, c in enumerate(s)}  # last occurrence of each char
    partitions = []
    start = max_end = 0
    for i, c in enumerate(s):
        max_end = max(max_end, last[c])
        if i == max_end:  # partition complete
            partitions.append(max_end - start + 1)
            start = i + 1
    return partitions

print(partition_labels('ababcbacadefegdehijhklij'))
# [9, 7, 8] — parts 'ababcbaca', 'defegde', 'hijhklij'

Riepilogo dei problemi sugli intervalli

Si padroneggino questi quattro schemi per gli intervalli: (1) Fusione: ordinare per inizio ed estendere l'ultimo intervallo in caso di sovrapposizione. (2) Conteggio delle sale: ordinare per inizio e usare un min-heap delle ore di fine. (3) Massimo numero di intervalli non sovrapposti: ordinare per fine e selezionare con una strategia greedy. (4) Inserimento: scansione lineare in tre fasi. La chiave di ordinamento è importante: la fusione usa l'inizio, mentre la selezione massima usa la fine. La complessità temporale è sempre O(n log n), dominata dall'ordinamento; fusione e scansione sono O(n).

# Quick reference:
# Merge intervals:         sort by start, extend if overlap
# Insert interval:         three-phase linear scan
# Meeting rooms (can?):   sort by start, check consecutive overlap
# Meeting rooms (min?):   sort by start, min-heap of end times / sweep
# Max non-overlapping:    sort by END, greedy keep
# Min removals:           n - max_non_overlapping
# Interval intersection:  two pointers on sorted lists

print('Pattern: sort key is the decisive choice')
print('Merge → sort by start')
print('Activity selection → sort by end')
print('Room count → sort by start + heap of ends')

Verifica rapida

Verifichi la propria comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.

Riepilogo della lezione

In questa lezione ha imparato a: fondere gli intervalli ordinandoli per inizio ed estendendo l'ultimo intervallo quando si verifica una sovrapposizione; calcolare il numero minimo di sale riunioni usando un ordinamento per inizio e un min-heap delle ore di fine, riutilizzando una sala quando quella che termina per prima è libera; e selezionare il numero massimo di intervalli non sovrapposti con una strategia greedy basata sull'ora di fine. Nella prossima lezione affronteremo Jump Game I e II: problemi di raggiungibilità e di numero minimo di salti risolti espandendo greedy l'intervallo raggiungibile.

Domande Frequenti

La lezione «Pianificazione e fusione degli intervalli» è gratuita?

Sì — il testo completo di «Pianificazione e fusione degli intervalli» è 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 «Pianificazione e fusione degli intervalli»?

Risolva i problemi meeting-rooms e non-overlapping-intervals ordinando per tempo di fine, e fonda gli intervalli nel problema merge-intervals ordinando per tempo di inizio. 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 2 di 4.

Quanto tempo richiede la lezione «Pianificazione e fusione degli intervalli»?

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

  1. Greedy e DP: quando usare ciascuno
  2. Pianificazione e fusione degli intervalli
  3. Jump Game I e II
  4. Task Scheduler e Gas Station
← Torna a Coding Interview Prep