// Intervals

core idea

Interval problems are array problems wearing a calendar costume: each element is a [start, end] pair, and before you write a single comparison, one question decides the whole solution — what do you sort by. Sort by start and every overlap becomes adjacent, so a single left-to-right sweep can fold ranges together. Sort by end and the earliest-finishing option becomes the provably safe greedy pick, so the same kind of sweep can choose among conflicting ranges instead. Almost everything else in this topic is one of those two sweeps, occasionally with a heap bolted on to track how many ranges are open at once.

when to reach for it

• The input is a list of [start, end] pairs — bookings, log windows, free/busy blocks, “meetings,” version ranges.
• You need to combine overlapping ranges into fewer, wider ones → sort by start, sweep once.
• You need to pick the largest non-conflicting subset, or count the minimum you’d remove → sort by end, greedy sweep.
• You need to know how many ranges are alive at the same instant (rooms, connections, workers) → sort by start, track live count with a heap of end times.
• Brute force compares every pair of intervals — O(n^2). One sort turns that into a single linear sweep.

universal templates

Merge — sort by start, extend the open run or close it and start a new one:

public int[][] MergeTemplate(int[][] intervals)
{
    Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));  // sort by START — merging only cares what runs into what

    var result = new List<int[]> { intervals[0] };
    for (int i = 1; i < intervals.Length; i++)
    {
        var last = result[^1];
        if (intervals[i][0] <= last[1])                // current starts before (or exactly when) last ends
            last[1] = Math.Max(last[1], intervals[i][1]);   // widen the open run to cover both
        else
            result.Add(intervals[i]);                   // no overlap — close the run, start a new one
    }
    return [.. result];
}

Select — sort by end, keep whatever doesn’t conflict with the last thing you kept:

public int SelectTemplate(int[][] intervals)
{
    Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));  // sort by END — greedy needs the earliest finisher first

    int kept = 0;
    int lastEnd = int.MinValue;
    foreach (var iv in intervals)
    {
        if (iv[0] >= lastEnd)          // doesn't conflict with the last interval you kept
        {
            kept++;
            lastEnd = iv[1];           // this is now the interval to beat
        }
    }
    return kept;                       // "minimum removals" = intervals.Length - kept
}

Every problem below is one of these two skeletons — sometimes with a min-heap layered on top of the merge template’s start-sort to track how many ranges are open at once, instead of merging them.

problems

Four problems, and every one of them is the merge template, the select template, or the merge template with a heap standing in for the single running interval:

1. 01Merge IntervalsmediumLC #56

   Sort by start; extend the current merged interval or start a new one.

2. 02Insert IntervalmediumLC #57

   Three phases: all-before, merge-overlapping, all-after.

3. 03Non-overlapping IntervalsmediumLC #435

   Sort by END — keep the interval that finishes earliest.

4. 04Meeting Rooms IImediumLC #253

   Min-heap of end times = rooms in use; peak heap size is the answer.