Merge Intervals Pattern
Overview
The Merge Intervals pattern deals with problems involving overlapping timeframes, schedules, or coordinate ranges. (e.g., Given meetings [1,3], [2,6], [8,10], merge the overlapping ones into [1,6], [8,10]).
The fundamental secret to mastering this pattern is Sorting. By sorting the array of intervals based entirely on their Start Time, you mathematically guarantee that any intervals that could possibly overlap must be immediately adjacent to each other in the array.
Once sorted, you iterate sequentially. If the start time of the current interval is less than or equal to the end time of the previous interval, they overlap! You merge them by updating the previous interval's end time to Math.max(previous.end, current.end). This guarantees an elegant O(N log N) solution.
Syntax
import java.util.*;
public class Intervals {
public int[][] merge(int[][] intervals) {
if (intervals.length <= 1) return intervals;
// 1. CRITICAL: Sort the 2D array by START time
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
// Add the first interval as our baseline
int[] currentInterval = intervals[0];
merged.add(currentInterval);
for (int[] interval : intervals) {
int currentEnd = currentInterval[1];
int nextStart = interval[0];
int nextEnd = interval[1];
// Do they overlap?
if (nextStart <= currentEnd) {
// Yes! Extend the baseline's end time to the max of both
currentInterval[1] = Math.max(currentEnd, nextEnd);
} else {
// No overlap. Move the baseline forward and add it to the list.
currentInterval = interval;
merged.add(currentInterval);
}
}
// Convert List back to 2D Array
return merged.toArray(new int[merged.size()][]);
}
}Common Pitfalls
- Forgetting to sort the array first. If the array is unsorted, overlapping intervals could be at opposite ends of the array, making sequential merging impossible.
- Sorting using basic subtraction
(a, b) -> a[0] - b[0]. If the times include massive negative integers, subtraction causes integer overflow. Always useInteger.compare(a[0], b[0])for safety. - Just taking the
nextEndon overlap. If interval A is[1, 10]and B is[2, 5], interval B is completely engulfed. If you set A's end to B's end, it shrinks to[1, 5]. You must useMath.max().
Interview Questions
O(N log N). The merging logic itself is an O(N) sequential loop, but the prerequisite step of sorting the intervals inherently takes O(N log N) time, which dominates the overall complexity.
Sort them by start time. Then iterate: if the start time of meeting i is strictly less than the end time of meeting i-1, they overlap, meaning the person cannot attend both. Return false.
Real-World Example
Calendar and Booking Applications (Google Calendar). When you want to find 'Free Time' across 5 different employees' schedules to book a meeting, the system collects all their busy intervals, merges the overlapping ones using this pattern, and then scans the gaps between the newly merged intervals to find available time slots.
public class CalendarManager {
public List<TimeSlot> findFreeTime(List<TimeSlot> allBusySlots) {
// Sort and merge all busy slots using Merge Intervals
List<TimeSlot> mergedBusy = mergeIntervals(allBusySlots);
List<TimeSlot> freeSlots = new ArrayList<>();
// The gaps between the merged busy slots are the free times
for (int i = 1; i < mergedBusy.size(); i++) {
TimeSlot previous = mergedBusy.get(i - 1);
TimeSlot current = mergedBusy.get(i);
// If there's a gap between previous end and current start
if (previous.end < current.start) {
freeSlots.add(new TimeSlot(previous.end, current.start));
}
}
return freeSlots;
}
}Check Your Knowledge
Test your understanding of Merge Intervals Pattern with these quick questions.