Pattern 12 of 27
Intervals
Sort intervals by start, then sweep once, merging or counting overlaps by comparing each start with the last end.
- Cost
- O(n log n) time for the sort, O(n) space
- Problems
- 6
When to reach for it
- The input is a list of [start, end] pairs.
- The prompt asks to merge, insert, remove overlaps, or count rooms or arrows.
- Two intervals only interact when one starts before the other ends.
How it works
After sorting by start time, an interval can only overlap the most recent interval you kept, so one pass decides everything. Merging extends that interval's end. Removing overlaps sorts by end instead and keeps whichever interval finishes first, which leaves the most room for the rest. Counting meeting rooms tracks how many intervals are open at once, either with a min-heap of end times or by sweeping sorted starts and sorted ends separately.
The template
Written for Merge Intervals (write-up)
def merge(intervals):
intervals.sort(key=lambda iv: iv[0])
out = []
for start, end in intervals:
if out and start <= out[-1][1]:
out[-1][1] = max(out[-1][1], end)
else:
out.append([start, end])
return outSix problems, in learning order
- 1.Merge IntervalsLeetCode 56Sort by start and keep extending the last end.Medium
- 2.Insert IntervalLeetCode 57Already sorted: copy intervals before, merge the overlapping middle, copy the rest.Medium
- 3.Meeting RoomsLeetCode 252PremiumSort and check whether any start comes before the previous end.Easy
- 4.Meeting Rooms IILeetCode 253PremiumA min-heap of end times; its largest size is the number of rooms.Medium
- 5.Non-overlapping IntervalsLeetCode 435Sort by end and count intervals that start before the kept end.Medium
- 6.Minimum Number of Arrows to Burst BalloonsLeetCode 452Sort by end and shoot one arrow at each end not already covered.Medium
What usually goes wrong
- Not deciding whether touching intervals such as [1, 4] and [4, 5] overlap; the prompt decides.
- Sorting by start for greedy removal, where sorting by end is what makes it correct.
- Sorting the input list in place when the caller still needs the original order.
Intervals, answered
When should I use the intervals pattern?
The input is a list of [start, end] pairs. The prompt asks to merge, insert, remove overlaps, or count rooms or arrows. Two intervals only interact when one starts before the other ends.
What is the time complexity of intervals?
O(n log n) time for the sort, O(n) space. Counting meeting rooms tracks how many intervals are open at once, either with a min-heap of end times or by sweeping sorted starts and sorted ends separately.
Which problem should I start with for intervals?
Start with Merge Intervals (LeetCode 56, Medium). Sort by start and keep extending the last end. The six problems on this page are in learning order.