Leetcode 56.合并区间【C++】

地址：https://leetcode-cn.com/problems/merge-intervals/

题目

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

解题思路

这题的思路不算难的，下面我的第一版代码也没花太多时间就写出来了。

第一版思路挺简单的，就是暴力解，遍历数组，把每一个区间的可能和它合并的区间都找出来和它合并，把合并了的区间直接删除。提交，超时，后来看了超时的输入数据，总共 10000 个区间……

然后我又想别的方法，起初写第一版代码的时候，我其实就有考虑对所有区间按区间的起始位置排序的，但是想着排序应该挺费时的，就没那么做。然后第一版超时了，想想其实排序了应该还好很多，因为按照初版代码的思路，每一次只考虑一个区间要把所有能合并的都找出来和它合并，这期间每新合并了一个区间，它都需要把剩下的所有区间重新遍历一次，复杂度已经是是指数级的了。但是如果先对区间排序，那么只需要考虑相邻区间是否需要合并即可，也就是说排序后的区间数组，只需要对它进行一次遍历即可。按照这个思路，写出了第二版先排序再合并的代码，然而还是超时了。

另外，在我的代码中，我为了节省内存，企图在原数组上修改，也就是两个区间合并到其中一个，然后把另一个删除。

后来我还是看了官方题解，其实官方题解跟我排序的思路就几乎是一样的了，看了之后才想明白，其实频繁的删除操作代价是很大的，毕竟每一次删除都要移动很多元素的位置，牺牲空间来换取时间是值得的。同时，我是真的傻了，明明 sort() 函数就可以直接对数组排序，我还自己写了一个排序……

代码

初版（超时）

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
		int i = 0;
		while (i < intervals.size())
		{
			int j = i + 1;
			while (j < intervals.size())
			{
				bool canMerge = (intervals[i][1] < intervals[j][0] || intervals[i][0] > intervals[j][1]) ? false : true;
				//把intervals[j]合并到intervals[i]
				if (canMerge) {
					intervals[i][0] = min(intervals[i][0], intervals[j][0]);
					intervals[i][1] = max(intervals[i][1], intervals[j][1]);

					intervals.erase(intervals.begin() + j);
					j = i + 1;
					continue;
				}
				j++;
			}
			i++;
		}
		return intervals;
    }
};

排序版（超时）

class Solution {
public:
	vector<vector<int>> merge(vector<vector<int>>& intervals) {
		//按区间的起始位置排序
		for (int i = 1; i < intervals.size(); i++) {
			int last = 0;
			for (int j = 0; j < intervals.size() - i; j++) {
				if (intervals[j][0] > intervals[j + 1][0]) {
					last = j;
					vector<int> tmp = intervals[j];
					intervals[j] = intervals[j + 1];
					intervals[j + 1] = tmp;
				}
			}
			i = intervals.size() - last - 1;
		}
		//合并
		int i = 1;
		while (i < intervals.size()) {
			if (intervals[i - 1][1] >= intervals[i][0]) {
				intervals[i - 1][1] = max(intervals[i - 1][1], intervals[i][1]);
				intervals.erase(intervals.begin() + i);
				continue;
			}
			i++;
		}
		return intervals;
	}
};

官方题解

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;
    }
};