最近AC题目的分析

1

题目

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

示例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] 可被视为重叠区间。

分析

  这种在数组空间上进行各种操作的题目，一般可以利用双指针进行解决。
  这个题目比较困难的地方再于各种边界的判定于操作，以及如何快速高效的进行合并。
  双指针再解决这类问题的时候总有着很清晰的思路，首先我们要减少复杂情况，所以先排序形成一个有序的状态。我们先设双指针
第一个$save$用于保留和扩展另一个用$scan$来进行扫描

  因为我们排序之后这个序列肯定是有序的所以我们就可以不用考虑左边界所有就剩下三种情况了

• eg: $\overbrace{[1,3],[4,5]}^{save}$这种情况最为简单，两个区间不相交，因此我们就可以把$save$指针所指向的数据压入result数组种，然后再将$save$移动到
  scan指针所指的地方：$[1,3],\overbrace{[4,5]}^{save}, \overbrace{[X,X]}^{scan}$

• $eg: \overbrace{[1,4]}^{save}, \overbrace{[2,3]}^{scan}$,这种是一种不被包含的情况，因此我们呢不需要操作$save$指针，$scan$ 指针继续往后移动即可：$\overbrace{[1,4]}^{save}, [2,3], \overbrace{[X,X]}^{scan}$

• $eg: \overbrace{[1,4]}^{save},\overbrace{[3,5]}^{scan}$,这种情况是相对比较复杂的情况，即我们需要对于$save$指针指向的数组进行扩展，所以我们需要修改数组为$\overbrace{[1,4]}^{save} \rightarrow \overbrace{[1,5]}^{save}$, 然后将$scan$指向下一个,也就是: $\overbrace{[1,5]}^{save}, [3,5], \overbrace{[X,X]}^{scan}$

代码

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // 对于特殊情况的特判
        if (intervals.size() == 0 || intervals.size() == 1) return intervals;

        // 双指针
        int save = 0; //用于保存的数组
        int scan = 0; // 用户扫描的数组

        vector<vector<int>> result;
        sort (intervals.begin(), intervals.end());

        while (scan < intervals.size()) {

            if (intervals[scan][0] > intervals[save][1]) {
                result.emplace_back(intervals[save]);
                save = scan;
            } else if (intervals[scan][1] <= intervals[save][1]) {
                ++ scan;
            } else {
                intervals[save][1] = intervals[scan][1]; //将数组扩充
                ++ scan;
            }

        }

        result.emplace_back(intervals[save]); // 当scan扫描到最后一个区间之后会跳出循环也就是说还有一个区间没有压入向量

        return result;
    }
};

思考

  三种情况种第一种情况是一般情况，后面两种是特殊情况，我们只需要对特殊情况经行处理称一般情况，然后让一般情况操就行了。