Interval Problems

TL;DR: Almost every interval problem starts by sorting, usually by start time, sometimes by end, then doing a single sweep. Once sorted, you compare each interval only to the running state (the last merged interval, or a count of currently-open intervals), which turns a naive O(n^2) all-pairs check into O(n log n). Merging, inserting, counting overlaps, and the meeting-rooms / minimum-resources problem are all the same sort-then-sweep skeleton with a different running state. If you find yourself comparing every pair, you skipped the sort.

Why sorting is the first move

Unsorted intervals force you to ask "does this overlap any other?", which is all-pairs and quadratic. Sorting imposes an order so that overlap becomes a local question: once intervals are sorted by start, anything that overlaps the current one is adjacent or already accounted for in your running state. You never look backward past the last relevant interval. That is the whole trick, and it is why the sort is reflexive: it costs O(n log n) and collapses the rest of the problem to a linear scan.

Two intervals [a, b] and [c, d] overlap when a <= d and c <= b. After sorting by start, the test simplifies to comparing each new start against the current end.

Merging overlapping intervals

Sort by start. Walk through; if the next interval starts at or before the current one ends, extend the current end to the max of the two ends. Otherwise close out the current interval and start a new one.

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])     # sort by start
    out = []
    for start, end in intervals:
        if out and start <= out[-1][1]:       # overlaps last merged
            out[-1][1] = max(out[-1][1], end) # extend, do not just take end
        else:
            out.append([start, end])
    return out

The edge case interviewers check: max(out[-1][1], end), not end. A fully-contained interval like [1, 9] followed by [2, 3] must not shrink the merged range. Candidates who write out[-1][1] = end pass the happy path and fail on nesting.

Inserting into a sorted list

Given already-sorted, non-overlapping intervals and one new interval, you do not need to re-sort. Three phases in one pass: copy intervals that end before the new one starts, merge everything that overlaps the new one (taking min start and max end), then copy the rest. That is O(n) because the input was already sorted, a nice signal that you noticed the precondition.

Counting overlaps and minimum resources

The meeting-rooms problem ("minimum rooms to host all meetings without conflict") is the maximum number of intervals open at any instant. Two clean approaches:

Event sweep. Split each interval into a +1 start event and a -1 end event, sort all events by time, sweep, and track the running sum. The peak of that running sum is the answer. Handle ties carefully: process an end at time t before a start at time t if a room frees exactly as the next begins.

Two sorted arrays / min-heap. Sort starts and ends separately, or push end times onto a min-heap; when a new meeting starts after the earliest end, reuse that room (pop), otherwise allocate a new one. The heap size peaks at the answer.

That last row is interval scheduling, where sorting by finish time is what makes the greedy choice optimal, a direct bridge to greedy algorithms.

Why interviewers probe this

Interval questions are a fast read on whether you default to sorting or to brute force. The strong-answer move is to say "sort by start, then sweep" before writing anything, then name the running state the specific problem needs. The held-back follow-up is usually the tie-breaking rule (does a meeting ending at t free the room for one starting at t?) and the streaming variant (intervals arriving in real time, where you cannot sort up front and need a heap or interval tree). Getting the max in the merge and the tie rule right is what separates a clean pass from a near-miss.

Common misconceptions

• "Compare every pair to find overlaps." That is O(n^2). Sorting makes overlap a local check and the whole thing O(n log n).
• "On merge, take the new interval's end." Use max(current_end, new_end); a contained interval must not shrink the range.
• "Min rooms means counting total overlapping pairs." It is the peak number of simultaneously open intervals, which a sweep or heap finds directly.
• "Sort by start for everything." Maximum non-overlapping intervals needs sorting by end time; the key depends on what you sweep for.

Key takeaways

• Sort first (usually by start, sometimes by end), then sweep once; that turns O(n^2) into O(n log n).
• Merge, insert, overlap-count, and min-rooms are one skeleton differing only in the running state.
• Use max(end1, end2) when merging so nested intervals do not shrink the result.
• Min resources equals the peak of simultaneously open intervals, found with an event sweep or a min-heap of end times.