Mesclar intervalos e linhas de varredura em C#

A família inteira gira em torno de uma escolha — ordenar pelo início, ou ordenar pelo fim. Mesclar quer uma, o guloso de agendamento quer a outra, e o código fica quase igual nos dois casos.

Intervalos são o padrão em que quase toda a dificuldade está na primeira linha. Quando eles estão na ordem certa, os algoritmos são curtos e óbvios. Na ordem errada, são curtos, óbvios e errados.

Todo programa abaixo é completo, foi rodado no .NET 10, e a saída está colada da execução.

Padrão 66 — Mesclando intervalos que se sobrepõem

Junte num único bloco todos os intervalos que se tocam.

Ordene pelo início. Depois disso, um intervalo novo só pode se sobrepor ao bloco que está sendo construído — nunca a um já terminado, porque tudo que terminou começou antes e este começa depois de todos eles.

(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}]"))}");

Ele 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]

A linha que importa é Math.Max(last.End, cur.End), não cur.End.

Se um intervalo curto fica inteiramente dentro de um longo — [1,10] e depois [2,3] — atribuir cur.End iria encolher o bloco para [1,3] e perder tudo depois de 3. Isso só aparece quando um intervalo fica aninhado dentro de outro, coisa que testes pequenos escritos na mão raramente contêm.

Se [1,3] e [3,5] contam como sobrepostos é uma decisão do problema, não sua. cur.Start <= merged[^1].End mescla os dois; < deixa os dois separados. Leia o enunciado.

Custo: O(n log n) para a ordenação, O(n) depois.

Use quando o problema diz mesclar, consolidar ou “combinar os que se sobrepõem”.

Padrão 67 — Inserindo numa lista ordenada

A lista já está ordenada e já não tem sobreposições. Insira mais um intervalo e mescle de novo.

A tentação é acrescentar no fim e rodar o padrão 66 de novo. Isso custa mais uma ordenação. Não é preciso — a ordem em que você ordenaria é a ordem que você já tem.

(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.");

Ele 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.

Três fases em linha reta, sem ordenação: copie tudo que termina antes do novo começar, absorva tudo que o toca, copie o resto.

A condição de absorção é intervals[i].Start <= merged.End, e merged.End cresce conforme absorve — então uma inserção pode engolir vários intervalos em sequência, que é exatamente o que acontece acima.

Custo: O(n), uma passada.

Use quando você está inserindo em, ou removendo de, um conjunto de intervalos que já é mantido em ordem.

Padrão 68 — Ordene pelo fim, não pelo início

Remova o menor número de intervalos para que nenhum dos restantes se sobreponha.

Essa é a mesma pergunta que manter o máximo de intervalos sem sobreposição, e aqui a chave de ordenação inverte.

(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.");

Ele 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 pelo início pega [1,100] primeiro, porque ele começa mais cedo — e esse único intervalo bloqueia todo o resto. Um fica, três saem.

Ordenar pelo fim pega o que termina mais cedo, o que deixa mais espaço para o que vem depois. Três ficam, um sai.

O fim mais cedo é a escolha gulosa, porque o quão cedo algo começa não diz nada sobre quanto espaço ele deixa atrás de si.

Esse é o argumento clássico de seleção de atividades, e é por isso que vale tratar essa família como dois padrões, não um. Mesclar quer ordem de início; agendar quer ordem de fim. Os laços parecem quase idênticos, então uma chave de ordenação errada produz uma resposta plausível e nenhum erro.

Custo: O(n log n).

Use quando o objetivo é encaixar o máximo possível, ou descartar o mínimo possível — agendamento de reuniões, intervalos sem sobreposição, “número máximo de eventos assistidos”.

Padrão 69 — Linhas de varredura

Quantas salas são necessárias para que duas reuniões nunca colidam?

Pare de pensar em intervalos. Cada reunião são dois eventos numa linha do tempo: um início que precisa de uma sala, e um fim que libera uma. Ordene todos os eventos por tempo e mantenha uma contagem corrente. O pico é a resposta.

(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.");

Ele 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) é o argumento de corretude inteiro, e é fácil de esquecer. No mesmo instante, um fim (-1) tem que ser processado antes de um início (+1). Uma reunião terminando às 10 e outra começando às 10 precisam de uma sala entre as duas, não duas. Ordene ao contrário e a contagem sobe por um instante, e o pico — que é a resposta — é exatamente o que uma subida momentânea estraga.

Isso é o array de diferenças da parte 3, numa linha do tempo em vez de um array, com as coordenadas sem compressão. Se os tempos fossem enormes e esparsos, o padrão 29 seria o próximo passo.

Custo: O(n log n) para a ordenação, O(n) para a varredura.

Use quando a pergunta é sobre simultaneidade — quantos ao mesmo tempo, o momento mais cheio, recursos mínimos. Não quantos se sobrepõem no total, mas quantos se sobrepõem simultaneamente.

Padrão 70 — Interseção de duas listas de intervalos

As duas listas estão ordenadas e sem sobreposições internas. Encontre todo trecho coberto pelas duas.

Essa é a caminhada de dois ponteiros da parte 1, com uma comparação diferente.

(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.");

Ele 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.

Dois fatos fazem todo o trabalho.

A sobreposição de dois intervalos é sempre [max(starts), min(ends)], e ela é vazia exatamente quando isso sai invertido — lo > hi. Uma expressão cobre o caso com e sem sobreposição, sem um teste separado para saber se eles se cruzam.

E você avança o intervalo que termina primeiro. Ele não pode se sobrepor a nada mais adiante na outra lista, porque tudo mais adiante começa depois de ele já ter terminado. Esse é o mesmo argumento de descarte do padrão 1, e é por isso que a caminhada é linear em vez de quadrática.

Custo: O(n + m).

Use quando duas agendas estão sendo comparadas — horários livres em comum, disponibilidade compartilhada, reservas que se sobrepõem.

O que lembrar

• Mesclar ordena pelo início. O guloso de agendamento ordena pelo fim. Nada no código vai dizer qual dos dois você escolheu, e os dois produzem saída plausível.

• Estenda com max(lastEnd, current.End). Atribuir current.End só quebra quando um intervalo fica aninhado dentro de outro.

• Se pontas que se tocam contam como sobreposição é decisão do problema. <= mescla [1,3] com [3,5]; < não.

• Uma lista já ordenada não precisa ser ordenada de novo. A inserção são três fases em linha reta e O(n).

• O fim mais cedo é a escolha gulosa. O quão cedo algo começa não diz nada sobre o espaço que ele deixa atrás.

• Uma linha de varredura transforma intervalos em eventos +1 e −1. Processe os fins antes dos inícios em tempos iguais, ou o pico sai errado.

• A sobreposição é [max(starts), min(ends)], vazia quando invertida. Uma expressão, sem teste de interseção separado.

A parte 15 é backtracking, que é um template e cinco problemas — e a linha que todo mundo esquece é a que desfaz o último movimento.