LeetCode435 无重叠区间

Ted

发布于：2020年12月31日
次浏览

435. 无重叠区间
452. 用最少数量的箭引爆气球
使用贪心算法解决区间问题。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/non-overlapping-intervals/ 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

435. 无重叠区间

题目描述

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

  • 可以认为区间的终点总是大于它的起点。
  • 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1:

输入: [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

题目解析

这道题看上去感觉还行，我第一时间想到的就是把区间看成一个一个的槽，让每个槽里只有一个元素，但这样过于抽象，不好实现。后来又想了想，觉得应该用排序，先将所有的区间按照区间开始位置进行排序，然后使用贪心算法，删除每一对相互重叠的两个区间中较大的一个。后来想了想，应该删除区间结束位置最大的一个。

这道题对我来说难点在于判断如何使用贪心算法，这里不太好想一个证明方法，我直接复制了LeetCode上的证明：

我们不妨想一想应该选择哪一个区间作为首个区间。
假设在某一种最优的选择方法中，[lk,rk] 是首个（即最左侧的）区间，那么它的左侧没有其它区间，右侧有若干个不重叠的区间。设想一下，如果此时存在一个区间 [lj,rj]，使得 rj < rk ，即区间 j 的右端点在区间 k 的左侧，那么我们将区间 k 替换为区间 j，其与剩余右侧被选择的区间仍然是不重叠的。而当我们将区间 k 替换为区间 j 后，就得到了另一种最优的选择方法。

有了证明后，程序实现的方法就很好想了，可以使用双指针的方法，一个指针指向当前节点，另一个指针指向下一个节点，然后判断两个节点所在的区间是否重叠。这里可以直接比较第一个区间的结尾与第二个区间的开始的大小，如果两个区间重叠，那么应该有后面的区间的开始位置<前面区间的结束位置。然后删除结束位置最大的节点，其实在实现时也并不需要真的删除节点，只要移动next指针就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int mincount = 0;
        //首先对区间数组按照区间开始的位置进行排序
        sort(intervals.begin(), intervals.end());
        //双指针
        int curr = 0, next = 1;
        while (next < intervals.size()) {
            //如果后面的区间的开始位置<前面区间的结束位置， 说明两区间有重叠
            if (intervals[curr][1] > intervals[next][0]) {
                mincount++;
                //比较两区间结束位置，删除结束位置最大的
                intervals[curr][1] > intervals[next][1] ? curr = next : curr = curr ;
                next++;
                continue;
            }
            else {
                //两区间不重叠，双指针向前移动
                curr = next;
                next++;
            }
        }
        return mincount;
    }
};

另外我在代码中遇到的错误就是忘记将curr设置为next的值，而是直接curr++，这样将导致curr移动到已经删除的节点上。

452. 用最少数量的箭引爆气球

题目描述

这道题的题干太长了而且描述的非常弱智，懒得在这抄了，直接放链接：

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4

题目解析

这道题跟上面一道题类似，都是要找到区间数组中的重叠区间，但这题对于重叠区间进行了限制，即要求所有的重叠区间全部包含一个值/区间，如果我们把这些区间纵向排列，可以想象成用一根箭贯穿他们或是用一根棍把它们串起来。一开始我也想使用与上一题类似的排序+双指针方法直接求解，可这回我发现答案却错误了，具体错误如下：

输入：[[9,12],[1,10],[4,11],[8,12],[3,9],[6,9],[6,7]]
输出：1
预期：2

可以发现，代码虽然可以通过题目示例里的几个测试用例，但是却不能通过这个用例，这是因为，除去输入数组的第一项[9,12]以外，其他的数组都可以覆盖一个区间[6,7]，而区间[9,12]显然不包含这一区间。我们在上一题中通过判断前一区间的右端点和下一区间的左端点的大小，来判断两个区间是否相互覆盖。但这题中我们就需要动态地修改右端点的大小，保证所有相互覆盖的区间都能覆盖到一个相同的区间，即“用一颗子弹贯穿这些区间”。

于是在第一份代码中，我们使用了r来表示当前区间的最右端点，并在每一次遍历到新的区间时动态修改r，保证所有的当前区间均能被一颗子弹贯穿。值得注意的是，每次遍历完一个这样的区间集合时，也就是在else中才将arrows加一，这样在最后一次遍历后arrows会少1，所以在最后返回arrows+1。

而在参考答案写出的第二份代码中，由于本题中判断区间是否可被子弹打穿，主要依据的是每一个区间的右端点值，因此可以使用一种贪心的思想，每次将子弹射入的位置设定为拥有最小右端点的区间的右端点值。于是我们可以将区间按照右端点大小进行排序，这里使用了C++中的lambda表达式方法，这个方法我还不是太熟悉，具体如何使用之后应该再了解一下。总之，将所有区间排序后，我们将最小的右端点设定为子弹射入的位置，并依旧向下遍历判断下一个区间的左端点，与当前射入位置的大小，这样就可以判断子弹是否能一次贯穿这两个区间了。

这个方法相比于最开始的代码，主要是在判断上节省了判断次数，因此消耗的时间也要明显少一些。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (!points.size()) return 0;
        int arrows = 0;
        sort(points.begin(), points.end());
        int curr = 0, next = 1;
        int r = points[0][1];
        while (next < points.size()) {
            if (points[next][0] <= r) {
                r = r >= points[next][1] ? points[next][1] : r;    
                next++;
                continue;
            }
            else {
                curr = next;
                r = points[curr][1];
                next++;
                arrows++;
            }
        }
        return arrows + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (!points.size()) return 0;
        int arrows = 1;
        sort(points.begin(), points.end(), [](const vector<int>& u, const vector<int>& v) {
            return u[1] < v[1];
        });
        int pos = points[0][1];
        for (int i = 1; i < points.size(); i++) {
            if (points[i][0] <= pos) continue;
            else {
                pos = points[i][1];
                arrows++;
            }
        }
        return arrows;
    }
};

最后更新于：2020年12月30日

LeetCode

贪心算法

评论