#56
Merge Intervals
Medium Sort by start
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Merge all overlapping intervals and return the non-overlapping result.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: merge overlapping intervals.
Why this works: after sorting by start, an interval either overlaps the last merged one (extend it) or starts a new one.
Example: [[1,3],[2,6],[8,10],[15,18]]
[1,3]+[2,6] → [1,6][8,10] new, [15,18] new
✦Hints open one at a time
Sort by start time.
Then each interval either overlaps the last merged one or starts a new one.
↗Approach
After sorting, keep the last merged interval. If the next start <= last end, extend the end with max; otherwise add a new interval.
</>Solution (Java)
import java.util.*;
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> res = new ArrayList<>();
for (int[] cur : intervals) {
if (res.isEmpty() || res.get(res.size() - 1)[1] < cur[0]) {
res.add(cur); // no overlap
} else {
int[] last = res.get(res.size() - 1);
last[1] = Math.max(last[1], cur[1]); // extend
}
}
return res.toArray(new int[0][]);
}
}!Common mistake
Setting end = next.end instead of max(end, next.end) — a nested interval would shrink the merged one.
Complexity
- Time: O(n log n).
- Space: O(n) for the output.
Topic: Sorting
🎬 Episodes 24–28: video coming soon