56. Merge Intervals
1. Description
Given a collection of intervals, merge all overlapping intervals.
2. Example
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
3. Constraints
- 1 <= intervals.length <= $10^4$
- intervals[i].length == 2
- 0 <= starti <= endi <= $10^4$
4. Solutions
Sort
n = intervals.size()
Time complexity: O(nlogn)
Space complexity: O(logn)
class Solution {
public:
vector<vector<int>> merge(const vector<vector<int>> &intervals) {
vector<vector<int>> sorted_intervals(intervals);
sort(sorted_intervals.begin(), sorted_intervals.end());
vector<vector<int>> merged_intervals;
for (int i = 0; i < sorted_intervals.size(); ++i) {
if (merged_intervals.empty() || merged_intervals.back()[1] < sorted_intervals[i][0]) {
merged_intervals.push_back(sorted_intervals[i]);
} else {
merged_intervals.back()[1] = max(sorted_intervals[i][1], merged_intervals.back()[1]);
}
}
return merged_intervals;
}
};