← All patternsMerge Intervals · template
Pattern · Greedy & Intervals
Merge Intervals
Sort intervals by start; each one either overlaps the last merged interval (extend it) or starts a new one.
Time O(n log n) · Space O(n)
Taught in Module 15: Intervals
Think of it like this
Combining meeting bookings in a calendar: sort them by start time, and any meeting that starts before the previous one ends joins it.
Clues that point here
- → Intervals, ranges, meetings, bookings
- → Merge overlapping
- → Insert an interval
- → Minimum rooms or arrows
Not this pattern when
- ✕ Intervals never overlap and are already sorted (simple scan)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
for (int[] cur : intervals) {
if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < cur[0]) merged.add(cur);
else merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], cur[1]);
}
return merged.toArray(new int[0][]);Common versions
- Merge intervals
- Insert interval
- Non-overlapping intervals
- Meeting rooms I and II
- Minimum arrows to burst balloons
Practice problems with this pattern
15.1Merge IntervalsMediummain pattern15.2Insert IntervalMediummain pattern15.3Meeting RoomsEasymain pattern15.4Meeting Rooms IIMediummain pattern15.5Non-overlapping IntervalsMediumalso uses it15.7Interval List IntersectionsMediumalso uses it33.6Partition LabelsMediumalso uses it