区间合并问题经常用排序来解决。
贪心O(NlogN)
/* * @lc app=leetcode id=56 lang=cpp * * [56] Merge Intervals */ // @lc code=start class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { int N = intervals.size(); vector<vector<int>> ans; if(N <= 0) return ans; sort(intervals.begin(),intervals.end(),[](vector<int>& a,vector<int>& b){return a[0]<b[0];}); ans.push_back(vector<int>{intervals[0][0],intervals[0][1]}); for(int i=1;i<N;i++){ if(ans.back()[1] < intervals[i][0]) ans.push_back(intervals[i]); else ans.back()[1] = max(ans.back()[1], intervals[i][1]); } return ans; } }; // @lc code=end