37: 合并区间

题目

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

思路

这道题我的思路完全正确，先把每段的左端点升序排列，然后用第一段做基准，后面i个首先用i的右端点和第一段的左端点比较
1.i <= 第一段，就直接把前一段写进二维数组
2.i > 第一段，i的右端点作为新的右端点base，以后用这个做比较

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size() <= 1){
            return intervals; 
        }
        vector<vector<int>> revArr;
        quickSort(0, intervals.size()-1,intervals);
        int staDex = 0;//开始处
        int enDex = 0;//结束处
        int base = intervals[0][1];//前面的里面最大的右值
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0] <= base){
                if(intervals[i][1] <= base){
                    continue;
                }
                else{
                    base = intervals[i][1];
                    enDex = i;
                }
                 if(i == intervals.size()-1){
                    vector<int>arr = {intervals[staDex][0],intervals[i][1]}; 
                    revArr.push_back(arr);
                }
            }
            else if(intervals[i][0] > base){
                    vector<int>arr = {intervals[staDex][0],intervals[enDex][1]}; 
                    revArr.push_back(arr);
                    staDex = i;
                    enDex = i;       
                if(i == intervals.size()-1){
                    vector<int>arr = {intervals[i][0],intervals[i][1]}; 
                    revArr.push_back(arr);
                } 
            }
        }
        return revArr;
    }
   //快速排序（从小到大）
void quickSort(int left, int right, vector<vector<int>>& arr)
{
	if(left >= right)
		return;
	int i, j, base;
    vector<int> temp;
	i = left, j = right;
	base = arr[left][0];  //取最左边的数为基准数
	while (i < j)
	{
		while (arr[j][0] >= base && i < j)
			j--;
		while (arr[i][0] <= base && i < j)
			i++;
		if(i < j)
		{
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	//基准数归位
	arr[left][0] = arr[i][0];
	arr[i][0] = base;
	quickSort(left, i - 1, arr);//递归左边
	quickSort(i + 1, right, arr);//递归右边
}
};

问题

1.排序排的太麻烦
2.只能写出部分输入，【1，10】，【2，4】，【4，6】这种没终止的地方

官方这个思路和我一样，实现代码却差太多

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) {
            return {};
        }
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;
        for (int i = 0; i < intervals.size(); ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (!merged.size() || merged.back()[1] < L) {
                merged.push_back({L, R});
            }
            else {
                merged.back()[1] = max(merged.back()[1], R);
            }
        }
        return merged;
    }
};

1. vector :: back()是“ vector”标头的库函数，用于访问矢量的最后一个元素，它返回对矢量的最后一个元素的引用。
2. 人家是和已经排好的最后返回的数组作比较，我是在前面还做变化比较，高下立见