【算法训练记录——Day37】

1.leetcode_56合并区间

思路：排序，如果重叠，更新right 为max(right, curVal), 不重叠就加入res,需要单独考虑最后一次，因为每次都是在下一次遍历开始时判断是否加入res，因此 当 i==size()时，单独考虑

	static bool cmp(const vector<int>& v1, const vector<int>& v2){return v1 < v2;}
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);int right = intervals[0][1];int left = intervals[0][0];vector<vector<int>> res;// for(auto i : intervals) {//     cout << i[0] << " " << i[1] << endl;// }vector<int> tmp;tmp.push_back(left);for(int i = 1; i <= intervals.size(); i++) {if(i == intervals.size()) {tmp.push_back(right);res.push_back(tmp);break;}// cout << i << " " << right << " ";if(right < intervals[i][0]) {tmp.push_back(right);res.push_back(tmp);tmp.clear();left = intervals[i][0];right = intervals[i][1];tmp.push_back(left);} else {right = max(right, intervals[i][1]);} cout << endl;;}return res;}