Intervals + Greedy · Stage 1 of 3
Sorting & Merging Overlapping Intervals
Sort by start time so overlapping intervals sit adjacent and merge in one scan
Foundations
An interval [start, end] covers every point from start to end. Two intervals a and b, with a starting first, overlap exactly when b.start <= a.end: b begins before a finishes. Interval problems usually begin by sorting on start, the adjacent-sweep idea from Sorting: once sorted, an interval that overlaps anything before it must overlap the last range built from those, so one scan is enough.
Merging sweeps the sorted list while building a list of merged ranges. If the next interval starts at or before the last range's end, it overlaps: extend that end to the larger of the two ends. Otherwise there is a gap, and the interval starts a new range. Each interval is compared once, with the last range only, so after the O(n log n) sort the scan is O(n).
Sort intervals = [[1, 4], [6, 9], [2, 5], [8, 11], [7, 10]] by start: [1, 4], [2, 5], [6, 9], [7, 10], [8, 11]. 2 <= 4, so the first range grows to [1, 5]; 6 > 5 starts [6, 9], which [7, 10] and [8, 11] extend to [6, 11]. The result is [[1, 5], [6, 11]].
[2, 5] overlaps [1, 4], and the next three chain into [6, 11], each starting before the range's current end.- Open lesson
Sorting
Interval problems start with a sort by start time. That lesson covers what it costs.
Case Scenario
The problem
Merge Intervals
Merge overlapping [start, end] intervals and return the covering list sorted by start.
- Input
- intervals = [[1, 3], [8, 10], [2, 6], [15, 18]]
- Output
- [[1, 6], [8, 10], [15, 18]]
Merge Intervals gives intervals in any order and asks for the merged, non-overlapping ranges that cover them. Sort by start, then fold each interval into the last range whenever its start is at or before that range's end. For intervals = [[1, 3], [8, 10], [2, 6], [15, 18]], sorting puts [2, 6] right after [1, 3], giving [[1, 6], [8, 10], [15, 18]].
The direct approach compares every pair, merges the first overlapping pair it finds, and starts over. Each merge removes one interval, but finding it can take O(n²) comparisons, so the whole process is O(n³). Unsorted, [2, 6] overlaps [1, 3] from two positions away, and nothing tells the scan where to look.
Approach 1 · Brute force
Merge pairs until none overlap
Scan every pair, merge the first overlapping pair into one interval, and restart the scan until a full pass finds no overlap.
Time O(n³) · Space O(n)
- 1def merge(intervals):
- 2 intervals = [list(x) for x in intervals]
- 3 changed = True
- 4 while changed:
- 5 changed = False
- 6 for i in range(len(intervals)):
- 7 for j in range(i + 1, len(intervals)):
- 8 a, b = intervals[i], intervals[j]
- 9 if a[0] <= b[1] and b[0] <= a[1]:
- 10 intervals[i] = [min(a[0], b[0]), max(a[1], b[1])]
- 11 intervals.pop(j)
- 12 changed = True
- 13 break
- 14 if changed:
- 15 break
- 16 return sorted(intervals)
Approach 2 · Sort, then sweep
Walkthrough
Same input, now one step at a time. Each frame highlights the line that runs and the values it changes.
- 1.Sort the intervals by start.
- 2.For each interval, if
mergedis not empty andstart <= merged[-1][1], setmerged[-1][1]to the larger end. - 3.Otherwise append the interval.
Python
Merge Intervals
- Input:
- intervals = [[1, 3], [8, 10], [2, 6], [15, 18]]
- Output:
- [[1, 6], [8, 10], [15, 18]]
- 1def merge(intervals):
- 2 intervals.sort(key=lambda x: x[0])
- 3 merged = []
- 4 for start, end in intervals:
- 5 if merged and start <= merged[-1][1]:
- 6 merged[-1][1] = max(merged[-1][1], end)
- 7 else:
- 8 merged.append([start, end])
- 9 return merged
Unsorted, [2, 6] overlaps [1, 3] but sits two places away from it. Comparing every pair would be needed to find that.
The Pattern
The invariant: after each step, merged holds disjoint ranges sorted by start, and the next interval can only overlap the last of them, because every earlier range ended before the last one began. One comparison per interval, extend or append, keeps that true.
From the trace
Merge Intervals
2 <= 3: [2, 6] starts before the last merged range ends. Extend its end to max(3, 6) = 6.Check it against the walkthrough. Sorting gave [1, 3], [2, 6], [8, 10], [15, 18]. [1, 3] started merged; 2 <= 3, so the range grew to [1, 6]. Then 8 > 6 and 15 > 10 each started a new range, for [[1, 6], [8, 10], [15, 18]].
The overlap test b.start <= a.end assumes a starts first, which the sort guarantees. Whether touching endpoints count depends on the problem: closed intervals merge [1, 4] and [4, 6], while half-open ones keep them apart.
Complexity
TimeO(n log n)
SpaceO(n)
The sort costs O(n log n), and the sweep is O(n), so the sort dominates. The merged list can hold all n intervals when none overlap: O(n) space.
Brute force
Merge pairs until stable
O(n³) time
O(n) space
This technique
Sort, then sweep
O(n log n) time
O(n) space
n=100
n=1,000
n=10,000
Comparisons on a log scale in the worst case.
When to use this in an interview
- Intervals arrive in any order, and overlapping ones must be combined.
- The output is a set of disjoint ranges that covers the input.
- Sorting by start is allowed, and
O(n log n)fits the budget.
In production
Finding a free slot on a calendar
To suggest a meeting time, a calendar app gathers every attendee's busy blocks, sorts them by start, and merges the overlaps, exactly as here. The gaps between the merged ranges are the times when everyone is free. Merging first means the app compares a handful of ranges instead of every attendee's events against every other's.
Where this breaks
After sorting by start, the next interval either extends the last range or starts a new one. A different order, or a rule that is not overlap, breaks that choice.
Your turn
Solve it yourself
You have watched a sort put every overlap next to the range it extends. Write it yourself on Merge Intervals, then splice one new interval into sorted ranges in Insert Interval, and merge each letter's span in Partition Labels.
- 1Solve it
Merge Intervals
Guided · the problem you traced above
- 2Insert IntervalOn your own · same pattern, no walkthrough
- 3Partition LabelsOn your own · same pattern, no walkthrough