Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
Constraints:
- 1 <= intervals.length <= 10^4
- intervals[i].length == 2
- 0 <= start_i <= end_i <= 10^4
Examples:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: The intervals [1,3] and [2,6] overlap, so they are merged into [1,6]. The intervals [8,10] and [15,18] do not overlap with any other intervals, so they remain the same.
Solutions
Sorting
The solution first checks if the input array is empty. If it is, it returns an empty array. Then, it sorts the intervals based on their start value. It initializes the result array with the first interval. Then, it iterates over the rest of the intervals. If the current interval overlaps with the last interval in the result array, it merges them by updating the end value of the last interval in the result array. If the current interval does not overlap with the last interval in the result array, it adds the current interval to the result array.
class Solution {
public: vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) return {
}
;
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
);
vector<vector<int>> result;
result.push_back(intervals[0]);
for (int i = 1;
i < intervals.size();
i++) {
if (intervals[i][0] <= result.back()[1]) {
result.back()[1] = max(result.back()[1], intervals[i][1]);
}
else {
result.push_back(intervals[i]);
}
}
return result;
}
}
;Follow-up:
What if the intervals are not sorted by their start value?
