Merge Intervals medium
Description
Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Examples
> Case 1:
Input: intervals = [[1,3], [2,6], [8,10], [15,18]]
Output: [[1,6], [8,10], [15,18]]
Explanation: [1,3] and [2,6] overlap, merge into [1,6].
> Case 2:
Input: intervals = [[1,4], [4,5]]
Output: [[1,5]]
Explanation: [1,4] and [4,5] are considered overlapping (they share endpoint 4).
> Case 3:
Input: intervals = [[1,4], [0,4]]
Output: [[0,4]]Constraints
1 <= intervals.length <= 10^4intervals[i].length == 20 <= start_i <= end_i <= 10^4
Approach
- Sort intervals by start time
- Walk through sorted intervals — if the current interval overlaps with the previous merged interval, extend it. Otherwise, start a new merged interval.
Two intervals [a, b] and [c, d] overlap if c <= b (when sorted by start).
Code
Explanation
After sorting by start time, we can process intervals left to right:
- If the current interval’s start is
<=the last merged interval’s end, they overlap. We extend the merged interval’s end to cover both. - If there’s a gap between them, we know no future intervals can overlap with the previous group (because we’re sorted), so we start a new merged interval.
Visual walkthrough with [[1,3], [2,6], [8,10], [15,18]]:
After sorting: [1,3], [2,6], [8,10], [15,18]
merged = [[1,3]]
[2,6]: 2 <= 3 (overlap) -> extend to [1,6]
merged = [[1,6]]
[8,10]: 8 > 6 (no overlap) -> add new
merged = [[1,6], [8,10]]
[15,18]: 15 > 10 (no overlap) -> add new
merged = [[1,6], [8,10], [15,18]]Sorting is the key. Without sorting, you’d need to compare every interval with every other interval (O(n^2)). Sorting lets us make the merge decision in a single left-to-right pass.
Analysis
- Time Complexity:
O(n log n)— dominated by the sort - Space Complexity:
O(n)— for the merged result (or O(log n) for the sort itself)