Merge, insert, and manipulate intervals by sorting and scanning.
The Overlapping Intervals pattern handles problems involving ranges defined by a start and end point. The core technique: sort intervals by start time, then scan through them, checking if the current interval overlaps with the previous one.
Sort by start time. For each interval, compare its start with the previous interval's end. If they overlap, merge them by extending the end. If they do not overlap, start a new group.
Overlapping bars on a timeline get merged into wider bars:
Why sort by start time? After sorting, you only need to compare adjacent intervals. If interval B starts after interval A ends, then no later interval can overlap with A either (since all later intervals have even larger start times). This single pass after sorting is what makes the pattern O(n log n).
Look for these signals in the problem statement. Any mention of ranges, intervals, or scheduling strongly suggests this pattern:
Two intervals [a, b] and [c, d] (sorted so a ≤ c) overlap when:
The sorting step is critical. Without sorting, you would need to compare every pair of intervals (O(n^2)). After sorting by start time, a single linear scan suffices because the sorted order guarantees that once an interval does not overlap, no future interval will overlap with the current merged group either.
The most classic interval problem. Sort by start, then scan through, merging any overlapping intervals by extending the end of the current merged interval.
Input: [[1,3], [2,6], [8,10], [15,18]]
// LeetCode #56 — Merge Intervals public int[][] merge(int[][] intervals) { // Step 1: Sort by start time Arrays.sort(intervals, (a, b) -> a[0] - b[0]); List<int[]> merged = new ArrayList<>(); for (int[] interval : intervals) { // No overlap: start a new interval if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) { merged.add(interval); } else { // Overlap: extend the end merged.get(merged.size() - 1)[1] = Math.max( merged.get(merged.size() - 1)[1], interval[1] ); } } return merged.toArray(new int[merged.size()][]); }
Why Math.max for the end? Consider [1,10] and [2,5]. The second interval is completely contained within the first. We need max(10, 5) = 10 to keep the larger end. Without max, we would incorrectly shrink the interval.
Given a sorted, non-overlapping list of intervals, insert a new interval and merge if necessary. The algorithm has three clean phases:
// LeetCode #57 — Insert Interval public int[][] insert(int[][] intervals, int[] newInterval) { List<int[]> result = new ArrayList<>(); int i = 0, n = intervals.length; // Phase 1: Add all intervals ending before newInterval while (i < n && intervals[i][1] < newInterval[0]) { result.add(intervals[i++]); } // Phase 2: Merge overlapping intervals while (i < n && intervals[i][0] <= newInterval[1]) { newInterval[0] = Math.min(newInterval[0], intervals[i][0]); newInterval[1] = Math.max(newInterval[1], intervals[i][1]); i++; } result.add(newInterval); // Phase 3: Add remaining intervals while (i < n) { result.add(intervals[i++]); } return result.toArray(new int[result.size()][]); }
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
No sorting needed! Unlike Merge Intervals, the input is already sorted and non-overlapping. The three-phase approach runs in O(n) time, which is optimal since we must examine every interval at least once.
These are the classic Overlapping Intervals problems you should practice:
Study order: Start with #56 (core merge pattern), then #57 (insert variant), then #252 (simple overlap check), then #253 (uses a min-heap for concurrent rooms), and finally #435 (greedy removal of minimum intervals).
Enter intervals as pairs (e.g., "1,3 2,6 8,10 15,18"). Watch them get sorted and merged step by step on a timeline.
The dominant cost is sorting the intervals: O(n log n). The merge scan itself is just O(n). We need O(n) space for the output list (in the worst case, no intervals overlap and we store all n).
Can we do better than O(n log n)? Not in general. To detect all overlaps, we need sorted order. However, if the input is already sorted (as in Insert Interval), we skip the sort and achieve O(n). For Meeting Rooms II, a min-heap adds O(n log n) for heap operations, matching the sort cost.