C++贪心算法——用最少数量的箭引爆气球、无重叠区间、合并区间

---

   一：用最少数量的箭引爆气球

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

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

   一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标(x处射出一支箭，若有一个气球的直径的开始和结束坐标为Xstart , Xend，且满足Xstart ≤ X ≤ Xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。
给你一个数组points ，返回引爆所有气球所必须射出的最小弓箭数。

   示例 1：

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

   示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

   示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。

   提示：

• 1 <= points.length <= 10^5
• points[i].length == 2
• -2^31 <= xstart < xend <= 2^31 - 1

–

   解题思路：

–

   ① 看到这道题，最先想到的是，直接按照每个区间的右端点进行排序，然后从头开始遍历排序后的队列。

   ② 此时队列中第一个元素的右端点，就是整个队列最靠左的右端点right，想要射掉该气球，必然要在right之前射一箭，同时这一箭会射掉所有左端点在射箭处或射箭处之前的所有气球，很显然，根据贪心的思想，射箭处选在最靠右的right处，射掉的气球最多。 所以，每次射箭点，必然选取在某个区间的右端点处。这些射掉的气球将被从队列中移除。本次射箭结束，射箭次数加1。

   ③ 重复执行上面的步骤②，直至队列为空，所有气球都被射掉了

   上述思路的参考程序如下：

class Solution {
public:
    static bool cmp(const vector<int>& a,const vector<int>& b)  { return a[1]<b[1]; }
   
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),cmp);
        // 因为涉及到大量的删除操作，为了将每个元素删除操作的时间复杂度
        // 从vector的O(n)降为list的O(1), 所以将 vector 转换为 list       
        list<vector<int>> points_list(points.begin(), points.end());
        int ans=0;
        while(!points_list.empty())
        {   
            // 注: list 是一个链表结构，不支持随机访问，这意味着你无法直接通过索引访问其元素。
            // points_list[0][1]是不被允许的
            int right=points_list.front()[1];   
            for(auto it= points_list.begin();it!=points_list.end();)
            { 
                if((*it)[0]<=right)  //注意：这里的(*it)中的()不能忽略，要先解引用得到vector<int>类型，再取其第一个元素
                {
                  it = points_list.erase(it); // 删除元素，并立即更新迭代器到下一个元素
                }
                else
                {
                    ++it; // 只有在不删除的情况下才手动递增迭代器
                }
            }

            ans++;
        }
        return ans;
    }
};

–

   上面的程序，有几点需要注意：

   1、由于程序中涉及大量的删除操作，vector容器的每进行一次删除操作时间复杂度是O(n)，很容易超时，因此，上面程序中在进行删除之前，将存放数据的容器更改为了list，list删除一个元素的时间复杂度是O(1)

   2、list 底层实现是链表结构，不支持随机访问，这意味着无法直接通过索引访问其元素。即，无法像vector那样使用 points_list[0][1]来访问points_list中的第一个元素，需要使用points_list.front()[1]来访问;

---

   改进解题思路：

–

   上面将被射掉的气球从队列中删除的思路，容易我们理解， 但是删除操作是很费时的，其实，我们完全没必要将其删除。

   按照右端点排序后，依然从头开始遍历排序后的队列，每轮射箭同样取队列中当前气球 （注意：因为不再进行删除，所以这里是根据索引值取的气球，除了第一次射箭外，不再是取第一个） 的右端点作为界限， 然后，若后面气球的左端点<=界限，则直接跳过（不再像之前那样将其从容器中移除了） ，若左端点>界限，则射箭数+1，并将该气球的右端点作为新的界限，循环执行以上过程。直至遍历结束

   上述改进思路的参考程序如下：

class Solution {
public:
    static bool cmp(const vector<int>& a,const vector<int>& b)  { return a[1]<b[1]; }
   
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),cmp);
        int ans=0,i=0;
        while(i<points.size())
        {
            int right=points[i][1];
            while( i<points.size() && points[i][0]<=right ) {i++;} 
            ans++; 
        }
        return ans;
    }
};

   其实，这道 用最少数量的箭引爆气球 的题，本质上就是在找给定的这一系列区间中的互不重叠的区间个数，需要特别注意的是，本题中设定l两个区间，仅某个端点重合时，也是重合的，例如区间[1,3] 和[3,4]是重合的，所以程序中points[i][0]<=right是带等于号的。

---

---

   二：无重叠区间

   435. 无重叠区间

   题目描述：给定一个区间的集合 intervals，其中每个 intervals[i] = [starti, endi]，求需要移除区间的最小数量，使得剩余区间不重叠。

   示例 1:

• 输入：intervals = [[1,2], [2,3], [3,4], [1,3]]
• 输出：1
• 解释：移除区间 [1,3] 后，剩下的区间不重叠。

   示例 2:

• 输入：intervals = [[1,2], [1,2], [1,2]]
• 输出：2
• 解释：你需要移除两个 [1,2] 来保证剩下的区间不重叠。

   示例 3:

• 输入：intervals = [[1,2], [2,3]]
• 输出：0
• 解释：你不需要移除任何区间，因为它们已经是互不重叠的了。

   提示：

• 1 <= intervals.length <= 10^5

• intervals[i].length == 2

• -5 * 10^4 <= starti < endi <= 5 * 10^4

   解题思路：

–

   看到这道题有没有很熟悉的感觉，其实他跟上面那道射气球的题是高度类似的，我在射气球那道题最后说了，最少射箭次数 其实就是在找互不重叠的区间个数，这道题找的是需要移除的区间数量，即，给定区间数量-互不重叠的区间个数。所以，有了之前的基础，这道题直接秒就可以了。

   但是需要注意的是，射气球那道题认为一个区间的右端点跟另一个区间左端点重合 算重叠区间，而这道题算不重叠区间，所以要去掉等于号：intervals[i][0]<right

   两道题的程序，仅存在两处细小的差异：

   容易得到参考程序如下：

class Solution {
public:
    static bool cmp(const vector<int>& a,const vector<int>& b)  { return a[1]<b[1]; }
   
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);
        int ans=0,i=0;
        while(i<intervals.size())
        {
            int right=intervals[i][1];
            while( i<intervals.size() && intervals[i][0]<right ) {i++;} 
            ans++; 
        }
        return intervals.size()-ans;
    }
};

---

---

   三：合并区间

   56. 合并区间

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

   示例 1：

输入：points= [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠，将它们合并为 [1,6]。

   示例 2：

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

   提示：

1 <= points.length <= 10^4
points[i].length == 2
1 <= starti <= endi <= 10^4

–

   解题思路：

–

   有了前面射气球那道题的基础，这道题同样可以快速秒了，思路都差不多，如下所示：

   ① 首先按照每个区间的左端点进行排序，然后从头开始遍历排序后的队列。

   ② 此时队列中第一个元素的左端点，就是整个队列最靠左的左端点left，且其右端点为right，遍历后续区间，若该区间的左端点小于right，必然是重叠区间，若当前区间的右端点大于right，此时需要对right更新，因为right存放的就是当前所有重叠区间的最右边界。继续遍历下一个，直至遍历到的区间的左端点大于right，说明当前遍历到的区间与前面遍历的所有区间均不重合。此时将{left,right}压入结果队列中，即前面所有重叠区间合并后的左右界限。然后将当前遍历到的区间的左右端点分别赋值给left,right，继续重复以上过程，遍历后续区间，直至所有区间遍历完成。

   容易得到参考程序如下：

class Solution {
public:
    static bool cmp(const vector<int>& a,const vector<int>& b)  { return a[0]<b[0]; }
   
    vector<vector<int>> merge(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),cmp);
        vector<vector<int>> ans; int i=0;
        while(i<points.size())
        {   
            int left=points[i][0];
            int right=points[i][1];
            while( i<points.size() && points[i][0]<=right ) 
            {   
                if(points[i][1]>right) right=points[i][1];
                i++;
            } 
            ans.push_back({left,right});
        }
        return ans;
    }
};

---