Hey.. I hope this helps.
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int n = intervals.size();
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
for (auto x : intervals) {
if (res.empty() || x.front() > res.back().back())
res.push_back(x);
else {
res.back()[1] = max(res.back()[1], x.back());
}
}
return res;
}
};Key points to remember:
- Sorting allows easy comparison of adjacent intervals.
- We only need to compare with the last interval in res.
- Overlapping occurs when the start of the current interval is <= the end of the last merged interval.
- When merging, we take the maximum of the current end and the new interval's end.
TC -> O( n log n + n )
SC -> O( n ) if counting result vector.