Intervals are the pattern where almost all of the difficulty is in the first line. Once they are in the right order the algorithms are short and obvious. In the wrong order they are short, obvious, and wrong.
Every program below is complete, was run on .NET 10, and its output is pasted from the run.
Pattern 66 — Merging overlapping intervals
Collapse any intervals that touch into single blocks.
Sort by start. After that, a new interval can only overlap the block currently being built — never one already finished, because everything finished began earlier and this one begins later than all of them.
The extension is max(lastEnd, current.End), not current.End. A short interval fully inside a long one would otherwise shrink the block — and that case only appears when one interval nests inside another.
(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}]"))}");It prints:
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]The line that matters is Math.Max(last.End, cur.End), not cur.End.
If a short interval sits entirely inside a long one — [1,10] then [2,3] — assigning cur.End would shrink the block to [1,3] and lose everything after 3. It only shows up when one interval nests inside another, which small hand-written test cases rarely contain.
Whether [1,3] and [3,5] count as overlapping is a decision the problem makes, not you. cur.Start <= merged[^1].End merges them; < leaves them separate. Read the statement.
Cost: O(n log n) for the sort, O(n) after.
Reach for it when the problem says merge, consolidate, or “combine overlapping”.
Pattern 67 — Inserting into a sorted list
The list is already sorted and already non-overlapping. Insert one more interval and re-merge.
The temptation is to append and re-run pattern 66. That costs another sort. It is not needed — the ordering you would sort into is the ordering you already have.
(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.");It prints:
[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.Three straight-line phases, no sorting: copy everything that finishes before the new one starts, absorb everything that touches it, copy the rest.
The absorb condition is intervals[i].Start <= merged.End, and merged.End grows as it absorbs — so one insertion can swallow several intervals in sequence, which is exactly what happens above.
Cost: O(n), single pass.
Reach for it when you are inserting into, or deleting from, a set of intervals that is already maintained in order.
Pattern 68 — Sort by the end, not the start
Remove the fewest intervals so that none of the rest overlap.
This is the same question as keep the most non-overlapping intervals, and here the sort key flips.
This is the whole difficulty of the interval family. Merging wants the intervals in start order; the scheduling greedy wants them in end order. The code is nearly identical, so nothing warns you when the sort key is the wrong one.
(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.");It prints:
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.Sorting by start takes [1,100] first, because it begins earliest — and that one interval blocks everything else. One kept, three removed.
Sorting by end takes whatever finishes soonest, which leaves the most room for what follows. Three kept, one removed.
Earliest finish is the greedy choice, because how early something starts says nothing about how much room it leaves behind it.
That is the classic activity-selection argument, and it is why this family is worth treating as two patterns rather than one. Merging wants start order; scheduling wants end order. The loops look nearly identical, so a wrong sort key produces a plausible answer and no error.
Cost: O(n log n).
Reach for it when the goal is to fit as many as possible, or drop as few as possible — meeting scheduling, non-overlapping intervals, “maximum number of events attended”.
Pattern 69 — Sweep lines
How many rooms are needed so that no two meetings collide?
Stop thinking about intervals. Each meeting is two events on a timeline: a start that needs a room, and an end that frees one. Sort all the events by time and keep a running count. The peak is the answer.
Stop thinking about intervals and think about events on a timeline. A start adds one, an end removes one, and the running maximum is the answer — the same idea as the difference array in part 3.
(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.");It prints:
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) is the whole correctness argument, and it is easy to leave out. At the same timestamp, an end (-1) must be processed before a start (+1). A meeting finishing at 10 and another starting at 10 need one room between them, not two. Sort them the other way round and the count momentarily spikes, and the peak — which is the answer — is exactly what a momentary spike corrupts.
This is the difference array from part 3, on a timeline instead of an array, with the coordinates left uncompressed. If the times were huge and sparse, pattern 29 would be the next step.
Cost: O(n log n) for the sort, O(n) for the sweep.
Reach for it when the question is about concurrency — how many at once, the busiest moment, minimum resources. Not how many overlap in total, but how many overlap simultaneously.
Pattern 70 — Intersecting two lists of intervals
Both lists are sorted and internally non-overlapping. Find every stretch covered by both.
This is the two-pointer walk from part 1, with a different comparison.
(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.");It prints:
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.Two facts do all the work.
The overlap of two intervals is always [max(starts), min(ends)], and it is empty exactly when that comes out backwards — lo > hi. One expression handles both the overlapping and non-overlapping cases, with no separate test for whether they intersect.
And you advance whichever interval ends first. It cannot overlap anything later in the other list, because everything later starts after it has already finished. That is the same discarding argument as pattern 1, and it is why the walk is linear rather than quadratic.
Cost: O(n + m).
Reach for it when two schedules are being compared — common free time, shared availability, overlapping bookings.
What to remember
-
Merging sorts by start. The scheduling greedy sorts by end. Nothing in the code will tell you which one you picked, and both produce plausible output.
-
Extend with
max(lastEnd, current.End). Assigningcurrent.Endbreaks only when one interval nests inside another. -
Whether touching endpoints count as overlapping is the problem’s decision.
<=merges[1,3]with[3,5];<does not. -
An already-sorted list does not need sorting again. Insertion is three straight-line phases and O(n).
-
Earliest finish is the greedy choice. How early something starts says nothing about the room it leaves behind.
-
A sweep line turns intervals into +1 and −1 events. Process ends before starts at equal times, or the peak is wrong.
-
The overlap is
[max(starts), min(ends)], empty when reversed. One expression, no separate intersection test.
Part 15 is backtracking, which is one template and five problems — and the line everyone leaves out is the one that undoes the last move.