Intermediate · Module 15 · Lesson 3
Merge intervals
Sort ranges and maintain the current merged end.
Lesson 85 of 123
1d streakInterval Scheduling: Sorting by Start Time & Merging Overlaps
To merge overlapping intervals, sort them by start time: interval[i][0]. Because start times are monotonic, any overlap must occur with the immediately preceding merged interval. Two intervals [s1, e1] and [s2, e2] overlap if s2 <= e1.
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
for (int[] interval : intervals) {
if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
merged.add(interval); // No overlap; append new interval
} else {
// Overlap detected; extend end time of last interval
merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
}
}
return merged.toArray(new int[merged.size()][]);
}Active Recall Checkpoint
Why is Integer.compare(a[0], b[0]) safer than a[0] - b[0] when sorting intervals?
Show answer & explanation
Subtraction can suffer 32-bit signed integer underflow/overflow if intervals contain extreme values like Integer.MIN_VALUE or Integer.MAX_VALUE.
Use it when
Use interval sorting for calendar scheduling, meeting rooms, non-overlapping interval removal, and free time slot detection.
Reconsider when
Reconsider when intervals arrive as continuous streaming queries; use an Interval Tree or Segment Tree for dynamic range queries.
Cost Model
Complexity & Trade-offs
When to use it
- Autocomplete, dictionary prefixes, wildcard matching, overlap, and scheduling.
- Sharing common string prefixes.
- Reducing range problems to ordered start/end events.
Common mistakes
- Forgetting terminal markers in a trie.
- Treating touching intervals as overlap without checking the problem convention.
- Processing equal-time events in the wrong order.
Practice prompts
- Reproduce the worked Merge intervals example without looking at the trace.
- Change one input condition and explain whether the Merge intervals invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check