Interval problems look varied, but many reduce to one idea: sort by start time, then sweep through once while maintaining the interval you are currently building.
The template
Sort the intervals by start. Place the first interval in a result list. For each next interval, compare its start with the end of the last result interval. If the start is less than or equal to that end, the intervals overlap, so extend the last end to the larger of the two ends. Otherwise, append the new interval as a separate one.
sort intervals by start
merged = [intervals[0]]
for current in intervals[1:]:
last = merged[-1]
if current.start <= last.end:
last.end = max(last.end, current.end)
else:
merged.append(current)Complexity
Sorting costs O(n log n), and the sweep costs O(n), so the total is O(n log n). The result list needs O(n) space in the worst case.
Edge cases that decide the answer
- Touching intervals: does [1, 3] merge with [3, 5]? Clarify whether endpoints are inclusive.
- Nested intervals: [1, 10] contains [2, 4]. Taking the maximum end handles this correctly.
- Unsorted input: never assume the intervals arrive in order.
- Empty input: return an empty list before reading the first element.
Related problems
Inserting a new interval into a sorted list follows the same sweep. Counting the minimum number of meeting rooms needs the maximum number of overlaps at one time, which you can find with a min-heap of end times or by sorting starts and ends separately.
Continue with the book
Explore the full treatment, worked examples, and exercises in Algorithmic Edge.
Adapted from Algorithmic Edge, published by Choral Software. Article text and original examples © 2026 Choral Software. All rights reserved.