Intervals + Greedy
How Intervals + Greedy works
Before you start
- Open lesson
Sorting
Interval problems start with a sort by start time. That lesson covers what it costs.
Why it matters
Calendars, IP allocations, hotel bookings, and genomic regions all accumulate ranges that may overlap. Repeatedly comparing every pair and restarting after each merge becomes cubic as the collection grows. The ranges must be normalized into disjoint coverage without repeatedly rescanning unrelated pairs.
Real-world constraint
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.
Example
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]]
Approach 1 · Brute force
Merge pairs until none overlap
Same example
intervals = [[1, 3], [8, 10], [2, 6], [15, 18]]
Scan every pair, merge the first overlapping pair you find, and start over. Each merge removes one interval, but finding it can take O(n²) checks.
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 · Resolve the bottleneck
The idea
Keep one example in view
Merge Intervals
intervals = [[1, 3], [8, 10], [2, 6], [15, 18]]→[[1, 6], [8, 10], [15, 18]]
The baseline, Merge pairs until none overlap, is O(n³) · O(n). The better model below keeps this exact input and removes that bottleneck.
For [[1, 3], [8, 10], [2, 6], [15, 18]], brute force searches all pairs again after each merge. Sorting places [2, 6] beside [1, 3], so one sweep extends them to [1, 6] and compares only the latest merged range.
Sort [[1, 3], [8, 10], [2, 6], [15, 18]] into [[1, 3], [2, 6], [8, 10], [15, 18]]. Start merged with [1, 3]. Because 2 ≤ 3, [2, 6] overlaps it, so extend the end to max(3, 6) = 6.
Next, 8 > 6, so [8, 10] begins a new range. Likewise, 15 > 10, so [15, 18] begins another. Sorting guarantees that the current interval cannot overlap an earlier range without also meeting the last merged one.
Visual anchor
Merge Intervals
Run the same example
Walkthrough
- 1.Sort the intervals by start.
- 2.For each interval, if merged is not empty and start ≤ merged[-1][1], set merged[-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.
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.
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.
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.
Your turn
Merge Intervals
Same problem, your code.
Solve Merge IntervalsThen branch out
Same technique, different problems. Try them without the walkthrough.