Merge Intervals
Sort intervals by start, then sweep merging overlaps.
Overlapping ranges, meeting rooms, calendar conflicts, interval insertion.
Sorting intervals by start time dominates at n log n; the merge sweep itself is linear. Space is O(n) for the output list of merged intervals (O(1) extra if merging in place).
Sorting intervals by start coordinate turns overlap detection into a linear sweep: once sorted, the only interval that can overlap the current 'open' interval is the next one. You either extend the open interval's end (overlap) or close it and start a new one (no overlap). Total cost is O(n log n) from the sort, O(n) for the sweep.
The overlap test itself is subtle: 'overlap' usually means current.start <= open.end, but 'touching' intervals like [1,2] and [2,3] may or may not count as overlapping depending on the problem (closed vs half-open intervals). Read the problem twice.
Variations decide what to do at the merge step. Merging unions the endpoints; counting meeting rooms uses a sweep-line with start/end events instead; interval insertion can skip the sort and do a three-phase walk (before, overlap, after). The pattern's general framing — sort by one coordinate, sweep maintaining state — is the precursor to sweep-line algorithms in computational geometry.
Sorting by start coordinate guarantees that any future interval overlapping the current open interval must arrive next, reducing all-pairs overlap detection from O(n^2) to a single O(n) sweep after the O(n log n) sort.
- Sorting by end instead of start (or vice versa) and getting greedy-scheduling vs merging confused.
- Using < instead of <= in the overlap test, missing touching intervals when they should merge.
- Mutating the input array's intervals in place when the problem expects a new list.
- For insert-interval, forgetting that the new interval may merge with multiple existing intervals (loop, don't single-step).
- For meeting-rooms-II, trying to merge intervals instead of using a min-heap of end times or a start/end event sweep.
- Merge all overlapping intervals: sort by start, sweep with one open interval.
- Insert interval into sorted non-overlapping list: three-phase walk, no resort needed.
- Meeting rooms II / minimum rooms: min-heap of end times, or sweep-line with +1/-1 events.
- Interval intersection of two sorted lists: two pointers, advance whichever ends first.
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> merged = new ArrayList<>();
for (int[] iv : intervals) {
if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < iv[0]) {
merged.add(iv);
} else {
merged.get(merged.size() - 1)[1] =
Math.max(merged.get(merged.size() - 1)[1], iv[1]);
}
}
return merged.toArray(new int[0][]);Problems using this pattern
3Easiest first · Blind 75 above NeetCode 150