source: https://leetcode.com/problems/merge-intervals
C/C++ Solution to LeetCode problem 56. Merge Intervals.
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.
Examples
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] overlap, 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.
Constraints
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
Solution
We need to sort the initial vector, so that every range will have a starti
value >=
than the previous range.
- Once sorted, we push the first range to the result.
- We iterate through all the next elements.
- If
starti >= starti-1
- If
endi >= endi-1
we have a new end for the last element in the results.
- If
- If not, we have a new range to add to the results.
- If
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.size() == 0) return { {} };
vector<vector<int>> result;
sort(intervals.begin(), intervals.end());
result.push_back(intervals[0]);
for (int i=1; i<intervals.size(); i+=1) {
if (intervals[i][0] >= result[result.size()-1][0] &&
intervals[i][0] <= result[result.size()-1][1]) {
if(intervals[i][1] >= result[result.size()-1][1])
result[result.size()-1][1] = intervals[i][1];
} else {
result.push_back(intervals[i]);
}
}
return result;
}
};