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.
#1. Brute Force Approach
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int n = intervals.size();
sort(intervals.begin(), intervals.end());
vector<vector<int>> ans;
for(int i = 0; i < n; i++) {
int str = intervals[i][0];
int end = intervals[i][1];
if(!ans.empty() && end <= ans.back()[1]) {
continue;
}
for(int j = i+1; j < n; j++){
if(intervals[j][0] <= end){
end = max(end, intervals[j][1]);
} else{
break;
}
}
ans.push_back({str,end});
}
return ans;
}
};
#2. Optimized Approach
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int n = intervals.size();
sort(intervals.begin(), intervals.end());
vector<vector<int>> ans;
for(int i = 0; i < n; i++) {
if(ans.empty() || intervals[i][0] > ans.back()[1]){
ans.push_back(intervals[i]);
} else{
ans.back()[1] = max(ans.back()[1], intervals[i][1]);
}
}
return ans;
}
};