贪心算法

发表于 分类于 ， 阅读次数： Waline： 本文字数： 5k 阅读时长 ≈ 5 分钟

什么是贪心算法呢？贪心算法可以认为是动态规划算法的一个特例，相比动态规划，使用贪心算法需要满足更多的条件（贪心选择性质），但是效率比动态规划要高。

比如说一个算法问题使用暴力解法需要指数级时间，如果能使用动态规划消除重叠子问题，就可以降到多项式级别的时间，如果满足贪心选择性质，那么可以进一步降低时间复杂度，达到线性级别的。

什么是贪心选择性质呢，简单说就是：每一步都做出一个局部最优的选择，最终的结果就是全局最优。注意哦，这是一种特殊性质，其实只有一小部分问题拥有这个性质。

比如你面前放着 100 张人民币，你只能拿十张，怎么才能拿最多的面额？显然每次选择剩下钞票中面值最大的一张，最后你的选择一定是最优的。

435. 无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例：

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]

输出: 1

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

思路：

举个例子，intvs=[[1,3],[2,4],[3,6]]，这些区间最多有两个区间互不相交，即[[1,3],[3,6]]，你的算法应该返回 2。注意边界相同并不算相交。

这个问题在生活中的应用广泛，比如你今天有好几个活动，每个活动都可以用区间[start,end]表示开始和结束的时间，请问你今天最多能参加几个活动呢？

这个问题有许多看起来不错的解决思路，实际上都不能得到正确答案。比如说：

也许我们可以每次选择可选区间中开始最早的那个？但是可能存在某些区间开始很早，但是很长，使得我们错误地错过了一些短的区间。

或者我们每次选择可选区间中最短的那个？或者选择出现冲突最少的那个区间？这些方案都能很容易举出反例，不是正确的方案。

正确的思路其实很简单，可以分为以下三步：

  1. 从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。
  2. 把所有与 x 区间相交的区间从区间集合 intvs 中删除。
  3. 重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。

把这个思路实现成算法的话，可以按每个区间的end数值升序排序，因为这样处理之后实现步骤 1 和步骤 2 都方便很多:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int> >& intervals) {
        if(intervals.size() == 0 || intervals.size() == 1) return 0;
        //按照 end 升序排列
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){
            return a[1] < b[1];
        });
        //至少有一个区间不相交
        int count = 1;
        //排序后，第一个区间为 x
        int x_end = intervals[0][1];
        for(vector<int> intv : intervals){
            int start = intv[0];
            if(start >= x_end){
                //找到下一个选择的区间
                count++;
                x_end = intv[1];
            }
        }
        return intervals.size() - count;
    }
};

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]。

思路：

和前面差不多，也是按照end的升序来排列

  • 从points 中选择结束时间最早的一个区间x_end
  • 我们可以发现只要start 小于 x_end的都可以只需要一箭，所以当 start 大于 x_end时，箭的数量加一，并且改变x_end
  • 重复以上两个，知道points 为空

代码如下：

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() == 0) return 0;
        if(points.size() == 1) return 1;

        //按照 end 升序排列
        sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b){
            return a[1] < b[1];
        });
        //至少需要一根箭
        int count = 1;
        int x_end = points[0][1];
        for(vector<int> p : points){
            int start = p[0];
          	// 起点大于终点，箭的数量加一，更新新的终点
            if(start > x_end){
                count++;
                x_end = p[1];
            }
        }
        return count;
    }
};

1024. 视频拼接

你将会获得一系列视频片段，这些片段来自于一项持续时长为 time 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。

使用数组 clips 描述所有的视频片段，其中 clips[i] = [starti, endi] 表示：某个视频片段开始于 starti 并于 endi 结束。

甚至可以对这些片段自由地再剪辑：

例如，片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。 我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, time]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。

示例：

输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10

输出：3

解释：

选中 [0,2], [8,10], [1,9] 这三个片段。

然后，按下面的方案重制比赛片段：

将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。

现在手上的片段为 [0,2] + [2,8] + [8,10]，而这些覆盖了整场比赛 [0, 10]。

思路：

我们先按照起点升序排列，如果起点相同的话按照终点降序排列。原因如下：

  • 视频肯定是[0,time]，如果没有从 0 开始的肯定凑不齐。
  • 如果有几个短视频的起点相同，我们肯定选择最长的（终点最大）视频。

排序之后我们可以得到：

这样我们就可以确定，如果clips[0]是的起点是 0，那么clips[0]这个视频一定会被选择。

当我们确定clips[0]一定会被选择之后，就可以选出第二个会被选择的视频:

我们会比较所有起点小于clips[0][1]的区间，根据贪心策略，它们中终点最大的那个区间就是第二个会被选中的视频。

然后可以通过第二个视频区间贪心选择出第三个视频，以此类推，直到覆盖区间[0, T]，或者无法覆盖返回 -1。

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
27
28
29
30
31
class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int time) {
        //按照起点升序排列，如果起点相同，按照终点降序排列
        sort(clips.begin(), clips.end(), [](const vector<int>& a, const vector<int>& b){
            if(a[0] == b[0]){
                return a[1] > b[1];
            }
            return a[0] < b[0];
        });
        int res = 0;

        int curEnd = 0, nextEnd = 0;
        int i = 0, n = clips.size();
        while(i < n && clips[i][0] <= curEnd){
            //在第 res 个视频的区间内贪心选择下一个视频
            while(i < n && clips[i][0] <= curEnd){
                nextEnd = max(nextEnd, clips[i][1]);
                i++;
            }
            //找到下一个视频，更新 curEnd
            res++;
            curEnd = nextEnd;
            if(curEnd >= time){
                //已经可以拼出区间 [0,time]
                return res;
            }
        }
        return -1;
    }
};