Fusionar intervalos y líneas de barrido en C#

Los intervalos son el patrón donde casi toda la dificultad está en la primera línea. Una vez que están en el orden correcto, los algoritmos son cortos y obvios. En el orden equivocado son cortos, obvios y están mal.

Todos los programas de abajo están completos, se ejecutaron en .NET 10, y su salida está pegada de la corrida.

Patrón 66 — Fusionar intervalos que se traslapan

Colapsa en un solo bloque todos los intervalos que se tocan.

Ordena por el inicio. Después de eso, un intervalo nuevo solo puede traslaparse con el bloque que se está construyendo — nunca con uno ya terminado, porque todo lo terminado empezó antes y este empieza después que todos ellos.

(int Start, int End)[] intervals = [(8, 10), (1, 3), (15, 18), (2, 6), (9, 12)];

// Sort by START. After that, an interval can only ever overlap the one
// currently being built — never anything already finished.
var sorted = intervals.OrderBy(x => x.Start).ToArray();
Console.WriteLine($"sorted by start: {string.Join(" ", sorted.Select(x => $"[{x.Start},{x.End}]"))}\n");

List<(int Start, int End)> merged = [];
foreach (var cur in sorted)
{
    if (merged.Count > 0 && cur.Start <= merged[^1].End)
    {
        var last = merged[^1];
        int newEnd = Math.Max(last.End, cur.End);
        Console.WriteLine($"[{cur.Start},{cur.End}] starts at {cur.Start} <= {last.End}, so it touches [{last.Start},{last.End}]" +
                          $"  ->  extend end to max({last.End},{cur.End}) = {newEnd}");
        merged[^1] = (last.Start, newEnd);
    }
    else
    {
        Console.WriteLine($"[{cur.Start},{cur.End}] starts after the last one ended  ->  start a new block");
        merged.Add(cur);
    }
}

Console.WriteLine($"\nmerged: {string.Join(" ", merged.Select(x => $"[{x.Start},{x.End}]"))}");

Imprime:

sorted by start: [1,3] [2,6] [8,10] [9,12] [15,18]

[1,3] starts after the last one ended  ->  start a new block
[2,6] starts at 2 <= 3, so it touches [1,3]  ->  extend end to max(3,6) = 6
[8,10] starts after the last one ended  ->  start a new block
[9,12] starts at 9 <= 10, so it touches [8,10]  ->  extend end to max(10,12) = 12
[15,18] starts after the last one ended  ->  start a new block

merged: [1,6] [8,12] [15,18]

La línea que importa es Math.Max(last.End, cur.End), no cur.End.

Si un intervalo corto queda por completo dentro de uno largo — [1,10] y luego [2,3] — asignar cur.End encogería el bloque a [1,3] y perdería todo lo que hay después del 3. Solo aparece cuando un intervalo queda anidado dentro de otro, que es algo que los casos de prueba pequeños escritos a mano casi nunca contienen.

Que [1,3] y [3,5] cuenten como traslapados es una decisión del problema, no tuya. cur.Start <= merged[^1].End los fusiona; < los deja separados. Lee el enunciado.

Costo: O(n log n) por el ordenamiento, O(n) después.

Úsalo cuando el problema dice fusionar, consolidar o «combinar los que se traslapan».

Patrón 67 — Insertar en una lista ordenada

La lista ya está ordenada y ya no tiene traslapes. Inserta un intervalo más y vuelve a fusionar.

La tentación es agregarlo al final y volver a correr el patrón 66. Eso cuesta otro ordenamiento. No hace falta — el orden al que ordenarías es el orden que ya tienes.

(int Start, int End)[] intervals = [(1, 3), (6, 9), (12, 16)];
(int Start, int End) insert = (4, 10);

// The list is already sorted and non-overlapping, so no sort is needed at all.
// Three phases: everything strictly before, everything that touches, everything after.
List<(int Start, int End)> result = [];
int i = 0, n = intervals.Length;

while (i < n && intervals[i].End < insert.Start)
{
    Console.WriteLine($"[{intervals[i].Start},{intervals[i].End}] ends before {insert.Start} — copy it across");
    result.Add(intervals[i++]);
}

var merged = insert;
while (i < n && intervals[i].Start <= merged.End)
{
    Console.WriteLine($"[{intervals[i].Start},{intervals[i].End}] overlaps — absorb it");
    merged = (Math.Min(merged.Start, intervals[i].Start), Math.Max(merged.End, intervals[i].End));
    i++;
}
Console.WriteLine($"the absorbed block is [{merged.Start},{merged.End}]");
result.Add(merged);

while (i < n)
{
    Console.WriteLine($"[{intervals[i].Start},{intervals[i].End}] starts after — copy it across");
    result.Add(intervals[i++]);
}

Console.WriteLine($"\nresult: {string.Join(" ", result.Select(x => $"[{x.Start},{x.End}]"))}");
Console.WriteLine($"\nO(n), no sorting — the input order was already the answer's order.");

Imprime:

[1,3] ends before 4 — copy it across
[6,9] overlaps — absorb it
the absorbed block is [4,10]
[12,16] starts after — copy it across

result: [1,3] [4,10] [12,16]

O(n), no sorting — the input order was already the answer's order.

Tres fases en línea recta, sin ordenamiento: copia todo lo que termina antes de que empiece el nuevo, absorbe todo lo que lo toca, copia el resto.

La condición de absorción es intervals[i].Start <= merged.End, y merged.End crece a medida que absorbe — así que una sola inserción puede tragarse varios intervalos seguidos, que es justo lo que pasa arriba.

Costo: O(n), una sola pasada.

Úsalo cuando estás insertando en, o eliminando de, un conjunto de intervalos que ya se mantiene en orden.

Patrón 68 — Ordena por el final, no por el inicio

Elimina la menor cantidad de intervalos para que ninguno de los que quedan se traslape.

Esta es la misma pregunta que conservar la mayor cantidad de intervalos sin traslape, y aquí la clave de ordenamiento se invierte.

(int Start, int End)[] intervals = [(1, 100), (2, 3), (4, 5), (6, 7)];

// Keep as many non-overlapping intervals as possible; the rest are removals.
static int Keep((int Start, int End)[] xs, bool byEnd, bool trace)
{
    var order = byEnd ? xs.OrderBy(x => x.End).ToArray() : xs.OrderBy(x => x.Start).ToArray();
    if (trace) Console.WriteLine($"  order: {string.Join(" ", order.Select(x => $"[{x.Start},{x.End}]"))}");

    int kept = 0, lastEnd = int.MinValue;
    foreach (var x in order)
    {
        if (x.Start >= lastEnd)
        {
            kept++; lastEnd = x.End;
            if (trace) Console.WriteLine($"    take [{x.Start},{x.End}]   next must start at or after {lastEnd}");
        }
        else if (trace) Console.WriteLine($"    skip [{x.Start},{x.End}]   it starts before {lastEnd}");
    }
    return kept;
}

Console.WriteLine("sorted by START:");
int a = Keep(intervals, false, true);
Console.WriteLine($"  kept {a}, removed {intervals.Length - a}\n");

Console.WriteLine("sorted by END:");
int b = Keep(intervals, true, true);
Console.WriteLine($"  kept {b}, removed {intervals.Length - b}");

Console.WriteLine($"\nSorting by start takes [1,100] first because it begins earliest,");
Console.WriteLine($"and that one interval blocks everything else. Sorting by end takes");
Console.WriteLine($"whatever finishes soonest, which leaves the most room for what follows.");

Imprime:

sorted by START:
  order: [1,100] [2,3] [4,5] [6,7]
    take [1,100]   next must start at or after 100
    skip [2,3]   it starts before 100
    skip [4,5]   it starts before 100
    skip [6,7]   it starts before 100
  kept 1, removed 3

sorted by END:
  order: [2,3] [4,5] [6,7] [1,100]
    take [2,3]   next must start at or after 3
    take [4,5]   next must start at or after 5
    take [6,7]   next must start at or after 7
    skip [1,100]   it starts before 7
  kept 3, removed 1

Sorting by start takes [1,100] first because it begins earliest,
and that one interval blocks everything else. Sorting by end takes
whatever finishes soonest, which leaves the most room for what follows.

Ordenar por inicio toma [1,100] primero, porque es el que empieza más temprano — y ese solo intervalo bloquea todo lo demás. Uno conservado, tres eliminados.

Ordenar por final toma lo que termina más pronto, que es lo que deja más espacio para lo que sigue. Tres conservados, uno eliminado.

El final más temprano es la elección voraz, porque qué tan temprano empieza algo no dice nada sobre cuánto espacio deja detrás.

Ese es el argumento clásico de selección de actividades, y es la razón por la que vale la pena tratar a esta familia como dos patrones y no como uno. La fusión quiere orden por inicio; la planificación quiere orden por final. Los bucles se ven casi idénticos, así que una clave de ordenamiento equivocada produce una respuesta plausible y ningún error.

Costo: O(n log n).

Úsalo cuando la meta es acomodar la mayor cantidad posible, o descartar la menor cantidad posible — programación de reuniones, intervalos sin traslape, «máxima cantidad de eventos a los que se asiste».

Patrón 69 — Líneas de barrido

¿Cuántas salas hacen falta para que no choquen dos reuniones?

Deja de pensar en intervalos. Cada reunión son dos eventos en una línea de tiempo: un inicio que necesita una sala, y un final que libera una. Ordena todos los eventos por tiempo y lleva un conteo acumulado. El pico es la respuesta.

(int Start, int End)[] meetings = [(0, 30), (5, 10), (15, 20), (6, 8)];

// Stop thinking about intervals. Think about EVENTS on a timeline: a start
// adds a room, an end frees one. The peak is the answer.
var events = meetings
    .SelectMany(m => new[] { (Time: m.Start, Delta: +1), (Time: m.End, Delta: -1) })
    .OrderBy(e => e.Time).ThenBy(e => e.Delta)      // an end at time t before a start at t
    .ToArray();

int inUse = 0, peak = 0;
foreach (var e in events)
{
    inUse += e.Delta;
    peak = Math.Max(peak, inUse);
    Console.WriteLine($"t={e.Time,2}  {(e.Delta > 0 ? "start" : "end  ")}  rooms in use: {inUse}   peak {peak}");
}

Console.WriteLine($"\nrooms needed: {peak}");
Console.WriteLine();
Console.WriteLine("ThenBy(Delta) matters: at a shared time an END (-1) must be processed");
Console.WriteLine("before a START (+1), or a room that is being freed gets counted twice.");
Console.WriteLine("That is the difference between a meeting ending at 10 and one starting");
Console.WriteLine("at 10 needing one room or two.");

Imprime:

t= 0  start  rooms in use: 1   peak 1
t= 5  start  rooms in use: 2   peak 2
t= 6  start  rooms in use: 3   peak 3
t= 8  end    rooms in use: 2   peak 3
t=10  end    rooms in use: 1   peak 3
t=15  start  rooms in use: 2   peak 3
t=20  end    rooms in use: 1   peak 3
t=30  end    rooms in use: 0   peak 3

rooms needed: 3

ThenBy(Delta) matters: at a shared time an END (-1) must be processed
before a START (+1), or a room that is being freed gets counted twice.
That is the difference between a meeting ending at 10 and one starting
at 10 needing one room or two.

.ThenBy(e => e.Delta) es todo el argumento de corrección, y es fácil de olvidar. En la misma marca de tiempo, un final (-1) se tiene que procesar antes que un inicio (+1). Una reunión que termina en 10 y otra que empieza en 10 necesitan una sala entre las dos, no dos. Ordénalos al revés y el conteo sube un instante de más, y el pico — que es la respuesta — es justo lo que ese salto momentáneo arruina.

Este es el arreglo de diferencias de la parte 3, sobre una línea de tiempo en vez de un arreglo, con las coordenadas sin comprimir. Si los tiempos fueran enormes y dispersos, el patrón 29 sería el siguiente paso.

Costo: O(n log n) por el ordenamiento, O(n) por el barrido.

Úsalo cuando la pregunta es sobre concurrencia — cuántos a la vez, el momento más ocupado, el mínimo de recursos. No cuántos se traslapan en total, sino cuántos se traslapan al mismo tiempo.

Patrón 70 — Intersectar dos listas de intervalos

Las dos listas están ordenadas y sin traslapes internos. Encuentra cada tramo cubierto por ambas.

Este es el recorrido de dos punteros de la parte 1, con una comparación distinta.

(int Start, int End)[] a = [(0, 2), (5, 10), (13, 23), (24, 25)];
(int Start, int End)[] b = [(1, 5), (8, 12), (15, 24), (25, 26)];

// Both lists are already sorted, so this is the two-pointer walk from part 1.
List<(int, int)> result = [];
int i = 0, j = 0;

while (i < a.Length && j < b.Length)
{
    int lo = Math.Max(a[i].Start, b[j].Start);      // the later of the two starts
    int hi = Math.Min(a[i].End, b[j].End);          // the earlier of the two ends

    if (lo <= hi)
    {
        result.Add((lo, hi));
        Console.WriteLine($"a[{i}]=[{a[i].Start},{a[i].End}]  b[{j}]=[{b[j].Start},{b[j].End}]  ->  overlap [{lo},{hi}]");
    }
    else
    {
        Console.WriteLine($"a[{i}]=[{a[i].Start},{a[i].End}]  b[{j}]=[{b[j].Start},{b[j].End}]  ->  no overlap");
    }

    // Advance whichever ends first — it can never overlap anything later.
    if (a[i].End < b[j].End) i++; else j++;
}

Console.WriteLine($"\nintersections: {string.Join(" ", result.Select(x => $"[{x.Item1},{x.Item2}]"))}");
Console.WriteLine();
Console.WriteLine("The overlap of two intervals is always [max(starts), min(ends)],");
Console.WriteLine("and it is empty exactly when that comes out backwards.");

Imprime:

a[0]=[0,2]  b[0]=[1,5]  ->  overlap [1,2]
a[1]=[5,10]  b[0]=[1,5]  ->  overlap [5,5]
a[1]=[5,10]  b[1]=[8,12]  ->  overlap [8,10]
a[2]=[13,23]  b[1]=[8,12]  ->  no overlap
a[2]=[13,23]  b[2]=[15,24]  ->  overlap [15,23]
a[3]=[24,25]  b[2]=[15,24]  ->  overlap [24,24]
a[3]=[24,25]  b[3]=[25,26]  ->  overlap [25,25]

intersections: [1,2] [5,5] [8,10] [15,23] [24,24] [25,25]

The overlap of two intervals is always [max(starts), min(ends)],
and it is empty exactly when that comes out backwards.

Dos hechos hacen todo el trabajo.

El traslape de dos intervalos siempre es [max(starts), min(ends)], y está vacío exactamente cuando eso sale al revés — lo > hi. Una sola expresión cubre tanto el caso con traslape como el caso sin él, sin ninguna prueba aparte para saber si se intersectan.

Y avanzas el intervalo que termina primero. No puede traslaparse con nada posterior de la otra lista, porque todo lo posterior empieza después de que él ya terminó. Ese es el mismo argumento de descarte del patrón 1, y es la razón por la que el recorrido es lineal y no cuadrático.

Costo: O(n + m).

Úsalo cuando se comparan dos calendarios — tiempo libre en común, disponibilidad compartida, reservas que se traslapan.

Qué recordar

• La fusión ordena por inicio. El voraz de planificación ordena por final. Nada en el código te va a decir cuál elegiste, y las dos producen salidas plausibles.

• Extiende con max(lastEnd, current.End). Asignar current.End solo falla cuando un intervalo queda anidado dentro de otro.

• Que los extremos que se tocan cuenten como traslape es decisión del problema. <= fusiona [1,3] con [3,5]; < no.

• Una lista que ya está ordenada no se vuelve a ordenar. La inserción son tres fases en línea recta y O(n).

• El final más temprano es la elección voraz. Qué tan temprano empieza algo no dice nada sobre el espacio que deja detrás.

• Una línea de barrido convierte los intervalos en eventos +1 y −1. Procesa los finales antes que los inicios cuando los tiempos son iguales, o el pico sale mal.

• El traslape es [max(starts), min(ends)], vacío cuando sale invertido. Una expresión, sin prueba de intersección aparte.

La parte 15 es backtracking, que es una plantilla y cinco problemas — y la línea que todos olvidan es la que deshace el último movimiento.