Intervals: The Core Idea

Open your calendar for a busy day. There is a meeting from 9 to 10, one from 9:30 to 11, and lunch from 12 to 1. Without thinking, you see that the first two clash and lunch is free. You can see it because the calendar draws the meetings in time order. If the same meetings were a shuffled list of numbers, you would have to compare every pair.

That is the whole pattern. The input is a list of [start, end] pairs, the question is about how they overlap, and almost every solution begins with a sort. After sorting, an interval can only overlap the ones just before it, so a single left-to-right pass is enough.

How to recognise it

1. The input is pairs of start and end values. Meetings, bookings, numeric ranges, video segments, CPU jobs. A parameter like intervals: list[list[int]] where each inner list has two numbers is close to conclusive.
2. The verb is about overlap. Merge, insert, remove the fewest, count how many run at the same time, find free gaps, detect a clash.
3. "Given in no particular order". That is a hint, not a warning: it tells you the sort has not been done for you.

The constraints usually say n ≤ 10⁴ or 10⁵. Comparing every pair is O(n²) — 10¹⁰ steps at n = 10⁵ — so the expected answer is O(n log n): a sort followed by a linear scan.

To see what sorting buys, look at the brute force for merging. Without order, you compare every pair; after merging two, the new interval may now overlap one you already checked, so you start again. That is O(n³) in the worst case, and the restart loop is easy to get wrong. After sorting, it becomes one pass.

How it works

The overlap test. Work with closed intervals, where [1, 3] includes both 1 and 3. It is easier to derive when two intervals do not overlap. There are only two ways:

a ends before b starts:   a.end < b.startb ends before a starts:   b.end < a.start

So "no overlap" is a.end < b.start or b.end < a.start. Negate both sides — "not (X or Y)" is "not X and not Y" — and you get the overlap test:

def overlaps(a: list[int], b: list[int]) -> bool:    """Closed intervals: touching at one point counts as overlapping."""    return a[0] <= b[1] and b[0] <= a[1]

Both halves are needed. Take a = [1, 3] and b = [10, 12]. The first half, 1 <= 12, is true; only the second half, 10 <= 3, rejects the pair. Swap a and b and it is the other half that does the work. One half alone always misses one direction.

Every pair of intervals falls into one of six arrangements. Checking a condition against all six is how you test it on paper.

Why sorting shrinks the test to one comparison. Sort by start. Now if a comes before b, then a.start <= b.start, so arrangement 6 cannot happen and a.start <= b.end is automatically true. The test becomes one comparison: b.start <= a.end. And because every earlier interval has already been folded into the "open" interval, you only ever compare with one interval — the last one you kept. That is the invariant behind almost every solution in this section.

The touching case. Are [1, 2] and [2, 3] overlapping? There is no universal answer, and interviewers leave it open to see whether you ask. Merging numeric ranges usually says yes: the point 2 is in both, so they merge into [1, 3]. Meeting rooms usually says no: a meeting ending at 2 frees the room for one starting at 2. In code the difference is one character, <= or <. Ask, then write a comment on the line.

Variants

The sort key is the design decision, and the wrong one gives a wrong answer, not a slow one.

The templates

Template 1 — sort by start, keep one open interval.

1def merge(intervals: list[list[int]]) -> list[list[int]]:2    """Sort by start, then extend or close one open interval."""3    merged: list[list[int]] = []4    for start, end in sorted(intervals, key=lambda i: i[0]):5        if merged and start <= merged[-1][1]:    # overlaps the open interval6            merged[-1][1] = max(merged[-1][1], end)7        else:                                    # a gap: open a new interval8            merged.append([start, end])9    return merged

Line by line. sorted(..., key=lambda i: i[0]) sorts by start and leaves the caller's list untouched; the explicit key documents the decision even though tuples would sort by the first field anyway. merged[-1] is the open interval. If the next interval starts at or before its end, they overlap, and the open interval grows to max(old end, new end) — the max matters when the new interval sits fully inside the open one. Otherwise there is a gap, the open interval is finished, and the new one becomes the open one. The start of the open interval never changes, because it is already the smallest.

Template 2 — the event sweep. When the question is "how many at once", turn each interval into two events and sweep through time.

1def max_overlap(intervals: list[list[int]]) -> int:2    """Most intervals active at the same moment (touching does not overlap)."""3    events: list[tuple[int, int]] = []4    for start, end in intervals:5        events.append((start, 1))                # one more is active6        events.append((end, -1))                 # one fewer is active7    events.sort()                  # at equal times, -1 sorts before +18    active = best = 09    for _, change in events:10        active += change11        best = max(best, active)12    return best

The sort puts (9, -1) before (9, 1), so an interval that ends at 9 is closed before one that starts at 9 is opened. That makes touching intervals not overlap, which is what meeting rooms want. For the opposite convention, sort starts first. This template also handles weights — "how many people are in the building" — by adding a count instead of 1.

Complexity

Both templates are O(n log n) time, and the sort is all of it; the scan after it is O(n). Space is O(n) for the output or the event list, plus whatever the sort uses (Python's Timsort may need up to O(n)). When the input is already sorted, as in Insert Interval or two sorted lists, the whole problem is O(n), and re-sorting would be a mistake.

Where it goes wrong

1. Sorting by the wrong endpoint. Non-overlapping Intervals sorted by start, on [[1, 100], [2, 3], [3, 4]], keeps [1, 100] first and must then reject both others: 2 removals. Sorted by end, it keeps [2, 3] and [3, 4]: 1 removal, the right answer. The rule: start when you build left to right, end when you greedily keep whatever frees up soonest.

2. The touching convention left unstated. [1, 2] and [2, 3] merge in one problem and share a room in another. Ask in one sentence: "If one ends at 2 and the next starts at 2, do they overlap?" If you cannot ask, say your assumption out loud. A stated assumption costs one character to fix; a silent one costs the problem.

3. Changing the list while looping over it. Calling intervals.remove(...) inside for interval in intervals shifts every later item, so the loop skips one. Python gives a wrong answer; Java throws ConcurrentModificationException. Build a new list instead, as both templates do. And note that intervals.sort() changes the caller's list; sorted(intervals) does not.

4. Using the new end instead of max(old end, new end). Merging [1, 10] with [3, 5] must give [1, 10]. Writing merged[-1][1] = end shrinks it to [1, 5]. This bug passes every test where intervals happen to arrive in order of end, which is most hand-written tests.