关于区间问题的解

区间问题看起来和滑动窗口很像，但是我在做本次分享最后一题的时候，相通了一句话，从本质上来说，区间问题就是在求交集/并集的过程，我们只要先把区间分类给划分好，就可以解决大部分的问题了，再搞清楚所解题目到底是求交集还是并集，就迎刃而解了。

题目1（汇总区间 leetcode-228）

给定一个无重复元素的有序整数数组 nums 。

区间 [a,b] 是从 a 到 b（包含）的所有整数的集合。

返回恰好覆盖数组中所有数字的最小有序区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个区间但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

“a->b” ，如果 a != b
“a” ，如果 a == b

示例

1 2	输入：nums = [0,1,2,4,5,7] 输出：["0->2","4->5","7"]

解题思路

这道题首先可以先套我们刚刚的思路，思考他是求并集还是求交集，那么我们可以简单的看出来，他明显是在求并集的，从示例来看，就是将[0],[1],[2]合并，将[4],[5]合并，将[7]合并所以我们就可以求得解为["0->2","4->5","7"],具体过程见代码：

代码实现

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string>res;
        int right=1;
        int left=0;
        string temp;
        for(;right<=nums.size();right++){
            //这里用static_cast<long long>是因为随机示例里面有阴间选手
            if(right==nums.size()||static_cast<long long>(nums[right]) - nums[right - 1] != 1){
                if(left<right-1){
                    temp=to_string(nums[left])+"->"+to_string(nums[right-1]);
                }else{
                    temp=to_string(nums[right-1]);
                }
                
                res.push_back(temp);
                left=right;
            }
        }
        return res;
    }
};

题目2（合并区间 leetcode-56）

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

示例

1 2	输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]]

解题思路

我们依旧先思考，这到底是要求并集还是交集，那显然从题目里面就可以看出来是求并集的，故而，我们直接来看这个题，一开始我没想用sort对他先进行一个排序，因为我觉得会增加时间复杂度，那么后面我明显就发现，排序之后会好做一些，所以我就先对这个给出的示例进行了一个排序sort(intervals.begin(),intervals.end())排序之后就好做很多了。见代码：

代码实现

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int left=intervals[0][0];
        int right=intervals[0][1];
        vector<vector<int>>res;
        
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0]>right){
                res.push_back({left,right});
                left=intervals[i][0];
                right=intervals[i][1];
            }else
            left=min(left,intervals[i][0]);
            right=max(right,intervals[i][1]);
        }
        res.push_back({left,right});
        return res;
    }
};

题目3（插入区间 leetcode-57）

给你一个无重叠的，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi]表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end]表示另一个区间的开始和结束。

如果两个区间至少共享一个点，则认为它们是重叠的。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 intervals。

注意你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

示例

1 2	输入：intervals = [[1,3],[6,9]], newInterval = [2,5] 输出：[[1,5],[6,9]]

解题思路

这道题是卡的我有点久了的，因为我一直没有get到一个点，我可以将题目给我的newInterval作为一个变动的区间，然后我直接用这个给我的区间去比较示例区间，融合成新区间，如果这个新的区间，在题目以及我们变动过后的所谓原区间的左边，我们就可以先把这个newInterval插入到我们结果数组res，然后直接就把所有的剩余区间全部塞进res了，为什么可以这样呢？
原因在于我们的这个newInterval区间是一个一直在维护变动的区间，它的右区间是把题目中给出的newInterval数组融合进示例数组里面得来的（max（newInterval[1],interval[][1]）），如果这个数组是完全在后面的原区间的左边，那就说明，题目给的这个newInterval和后面的数组没有半毛钱的关系，就可以把后面的直接塞进去了（当然，我在这里没有考虑后面的区间并集的情况，能过就行）。
那我们同理可得，如果这个新的区间在题目以及我们变动过后的所谓原区间的右边的话，我们就可以先把前面的原区间填进去，然后再进行一个循环就行。
那有人就问了，主播主播，要是存在融合区间的情况怎么办呢，还需要写很多个if语句去判断吗，那完全是不用的，我们就直接掏出王炸newInterval[0] = min(newInterval[0], intervals[i][0]);,newInterval[1] = max(newInterval[1], intervals[i][1]);就可以直接解决这个问题了。具体看代码：

代码实现

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;

        if(intervals.empty()){
            return {newInterval};
        }

        for(int i = 0; i < intervals.size(); i++){

            if(newInterval[0] > intervals[i][1]){
                res.push_back(intervals[i]);
            }
            else if(newInterval[1] < intervals[i][0]){
                res.push_back(newInterval);

                while(i < intervals.size()){
                    res.push_back(intervals[i]);
                    i++;
                }

                return res;
            }
            else{
                newInterval[0] = min(newInterval[0], intervals[i][0]);
                newInterval[1] = max(newInterval[1], intervals[i][1]);
            }
        }

        res.push_back(newInterval);
        return res;
    }
};

题目4（用最小的箭射爆气球 leetcode-452）

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数。

示例

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

解题思路

那前三道题都是非常之明显的求并集，那这题我们就开始求交集了，那就有人要问了，主播主播，求并集和求交集有什么区别呢，有的，孩子有的，求并集是求最小的left和最大的right，求交集呢就是求最大的left和最小的right，这道题看着难，实际上我们只需要将题目2进行小小的改动，一切就豁然开朗了，只要把交集求出来，然后再返回ans就行。具体见代码：

代码实现

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end());
        int left=points[0][0];
        int right=points[0][1];
        vector<vector<int>>res;
        
        for(int i=1;i<points.size();i++){
            if(points[i][0]>right){
                res.push_back({left,right});
                left=points[i][0];
                right=points[i][1];
            }else
            left=max(left,points[i][0]);
            right=min(right,points[i][1]);
        }
        res.push_back({left,right});
        return res.size();
    }
};

易错点

做到这种题目呢，首先要扪心自问一下，这到底是要求交集，还是要求并集，然后再做完交集并集之后，又要想，有没有将最后的一个res填进结果里面，然后就解决问题了。