Intervals

An interval is just a pair [start, end] describing a contiguous range — a meeting from 9am to 10am, a byte range in a file, a span of matched IDs. Almost every interval problem hinges on one decision made up front: whether the endpoints are inclusive ([start, end], so an interval ending at 5 and one starting at 5 "touch" and may need to merge) or half-open ([start, end), so they don't touch at all). Get that decision wrong and your merge condition is off by one; always check the problem statement's examples for a case where two intervals share exactly one boundary point, since that's where the convention shows itself.

Once the representation is settled, the second decision is almost always: sort first. Intervals arrive in arbitrary order, and nearly every efficient interval algorithm depends on processing them in a specific sequence — usually sorted by start time. Sorting turns an "any interval could relate to any other interval" problem, which looks like it needs O(n^2) pairwise comparisons, into a single linear pass where you only ever need to compare neighboring intervals or track a small amount of running state. That's the whole trick: sorting imposes an order where a greedy, one-pass scan becomes correct.

There are three problem shapes that cover most of what shows up in interviews. Merging overlaps: given one list of intervals in any order, sort by start, then walk through combining any interval that overlaps (or touches, per your endpoint convention) the last one you've kept. Intersecting two lists: given two already sorted, disjoint lists (a common setup — think two people's separate calendars), walk both with a two-pointer sweep, emitting the overlap between the current pair whenever they intersect, and always advancing whichever interval ends first, since it can't overlap anything later. Sweep-line counting: to find the maximum number of intervals active at any single point (the "minimum meeting rooms" family), don't think of intervals at all — think of individual start and end events. Sort all the start times and end times together, walk through them in order, add 1 at each start and subtract 1 at each end, and track the running maximum. This turns "which intervals overlap which" into a simple counter, sidestepping the need to reason about interval relationships directly.

A generic merge template:

intervals.sort(key=lambda iv: iv[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
    if start <= merged[-1][1]:       # overlaps (or touches) the last kept interval
        merged[-1][1] = max(merged[-1][1], end)
    else:
        merged.append([start, end])

And a generic sweep-line event-counting template:

events = sorted([(s, +1) for s, e in intervals] + [(e, -1) for s, e in intervals])
running, best = 0, 0
for _, delta in events:
    running += delta
    best = max(best, running)

(In practice you also need a tie-break rule for events that share a timestamp — typically process ends before starts, or starts before ends, depending on whether touching counts as overlapping — see the pitfalls below.)

Complexity. Every one of these techniques costs O(n log n) for the initial sort, followed by a single O(n) linear pass, so the overall cost is O(n log n) time. Space is O(n) for the sorted copy or the event list (O(1) extra if you're allowed to sort in place and only need a count, not the merged intervals themselves).

Common pitfalls. Getting inclusive vs. exclusive endpoints backwards, so intervals that should merge don't (or vice versa); forgetting to sort both lists before a two-pointer intersection sweep (the two-pointer advance logic assumes each list is already ordered and disjoint); mishandling the tie-break when a start and an end share the same coordinate in a sweep-line count (decide up front whether an interval ending at t and one starting at t should be counted as simultaneously active); and not handling empty input, a single interval, or completely disjoint intervals as edge cases before assuming the general-case logic just works.

This subject walks through three problems built on these ideas: merging a list of overlapping intervals into the smallest equivalent set, finding the intersection between two sorted lists of disjoint intervals with a two-pointer sweep, and finding the maximum number of intervals overlapping at any single point with a sweep-line event count.