Intervals: sort, then sweep
Sort by start (or end) so overlaps become adjacent, then sweep once while comparing only with the last interval kept.
Merge Intervals. Given [start, end] pairs, merge all overlapping intervals and return the result sorted by start.
Signals that point here
- Meetings, bookings, time ranges, genomic ranges.
- "Minimum rooms", "insert interval", "non-overlapping", "free time".
- Anything where sorting by an endpoint makes the relevant comparison local.
The idea
After sorting by start, a new interval can only overlap the last interval in the output. Every earlier output interval ended before the last one began, and the new interval starts no earlier than the last one did.
So the sweep is one comparison: if start <= last_end, extend last_end to the max; otherwise start a new interval. Touching endpoints ([1,4] and [4,5]) count as overlapping here; confirm that with the interviewer.
def merge(intervals: list[list[int]]) -> list[list[int]]:
merged: list[list[int]] = []
for start, end in sorted(intervals):
if merged and start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return mergedpublic static class Intervals
{
public static List<int[]> Merge(int[][] intervals)
{
var merged = new List<int[]>();
foreach (var iv in intervals.OrderBy(iv => iv[0]))
{
if (merged.Count > 0 && iv[0] <= merged[^1][1])
merged[^1][1] = Math.Max(merged[^1][1], iv[1]);
else
merged.Add(new[] { iv[0], iv[1] });
}
return merged;
}
}Complexity
O(n log n) for the sort, then O(n) for the sweep. O(n) for the output.
Pitfalls interviewers watch for
- Setting
last_end = endinstead ofmax(last_end, end):[1,10]then[2,3]shrinks to[1,3]. - Not sorting, or sorting by end for a problem that needs start.
- Mutating the caller's input when sorting in place without saying so.
Variants worth knowing
- Meeting rooms II (minimum rooms): sort starts and ends separately, or a min-heap of end times.
- Non-overlapping intervals (fewest removals): sort by end and keep greedily; see the greedy lesson.
- Insert interval into a sorted, non-overlapping list in
O(n).
Test it like the interviewer will
merge([[1, 3], [2, 6], [8, 10], [15, 18]])returns[[1, 6], [8, 10], [15, 18]]merge([[1, 4], [4, 5]])returns[[1, 5]]merge([[4, 7], [1, 4]])returns[[1, 7]]merge([[1, 10], [2, 3], [4, 5]])returns[[1, 10]]merge([])returns[]- Say the cases out loud before you run them. OpenAI's published guide names test coverage as part of the bar; see Sources.
Step through it: merge([[8, 10], [1, 3], [15, 18], [2, 6], [9, 12]])
Each step is recorded from an instrumented copy of the Python above, run when the site was built.
Practice
Written for this site to drill the lesson. Not reported interview questions.
- Return the minimum number of meeting rooms needed for a list of meetings.
- Insert a new interval into a sorted list of disjoint intervals and merge as needed.
- Given two lists of disjoint intervals, return their intersections.
Check yourself
After sorting by start, which interval can a new one overlap?
Only the last one in the merged output.
What bug does max(last_end, end) prevent?
A contained interval shrinking the merged end, e.g. [1,10] then [2,3].