Problem
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Approach
If two interval intersects, then one of the intervals’ start will be in between of another interval’s start and end. To make the problem simpler, we sort the input intervals and iterate through it. If the current iterated interval does not overlap with any previous intervals, then the interval’s start will be greater than the end of merged interval (and so does the next, and the next after that). If there is an overlap, then merge.
Time complexity should be $O(n\log n)$.
Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
std::vector<std::vector<int>> merge(
std::vector<std::vector<int>>& intervals) {
std::vector<std::vector<int>> output;
std::sort(intervals.begin(), intervals.end());
for (auto i: intervals) {
if (output.empty() || i[0] > output.back()[1] )
output.push_back(i);
else {
output.back()[1] = std::max(i[1], output.back()[1]);
}
}
return output;
}
};