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.
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.
Example 3:
Input: intervals = [[4,7],[1,4]] Output: [[1,7]] Explanation: Intervals [1,4] and [4,7] are considered overlapping.
Constraints:
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104 class Solution {
public:
// Note - The optimal solution is to use an Interval Tree Data Structure
// Brute Force
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end());
vector<vector<int>> res;
if (intervals.size() == 1) return {intervals[0]};
for(int i=1; i<intervals.size(); i++){
cout << intervals[i-1][0] << " " << intervals[i-1][1] << " | ";
if(intervals[i-1][1]>=intervals[i][0]){
intervals[i][0] = intervals[i-1][0];
intervals[i][1] = max(intervals[i-1][1],intervals[i][1]);
continue;
}
res.push_back(intervals[i-1]);
}
res.push_back(intervals[intervals.size()-1]);
return res;
}
};class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int[] prev = intervals[0];
List<int[]> ans = new ArrayList<>();
for (int[] i : intervals) {
if (i[0] > prev[1]) {
ans.add(prev);
prev = i;
} else
prev[1] = Math.max(prev[1], i[1]);
}
ans.add(prev);
int[][] res = new int[ans.size()][2];
for (int i = 0; i < res.length; i++)
res[i] = ans.get(i);
return res;
}
}