贪心算法题

贪心选择性质

贪心选择性质，简单说就是：每一步都做出一个局部最优的选择，最终的结果就是全局最优。

使用贪心算法需要满足更多的条件（贪心选择性质），但是效率比动态规划要高。

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

区间调度问题

给你很多形如[start,end]的闭区间，请你设计一个算法，算出这些区间中最多有几个互不相交的区间。

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

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

把这个思路实现成算法的话，可以按每个区间的end数值升序排序

#include <gtest/gtest.h>

#include <algorithm>
using namespace std;

struct interval {
  int start;
  int end;
};

int intervalSchedule(vector<interval> intvs) {
  if (intvs.size() == 0) return 0;
  // 按 end 升序排序
  sort(intvs.begin(), intvs.end(), [](interval i1, interval i2) { return i1.end <= i2.end; });
  // 至少有一个区间不相交
  int count = 1;
  // 排序后，第一个就是end最小的区间
  int x_end = intvs[0].end;
  for (auto i : intvs) {
    if (i.start >= x_end) {
      count++;
      x_end = i.end;
    }
  }
  return count;
}

TEST(Algo, intervalSchedule) {
  vector<interval> intvs{
      interval{2, 4}, interval{1, 3}, interval{3, 6}, interval{6, 9}, interval{5, 8}};
  cout << intervalSchedule(intvs) << endl;
}

应用举例

leetcode 435

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

注意:

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

int eraseOverlapIntervals(vector<interval> intvs) {
    int n = intvs.length;
    return n - intervalSchedule(intvs);
}

leetcode 452

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

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

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

分析：

其实稍微思考一下，这个问题和区间调度算法一模一样！如果最多有n个不重叠的区间，那么就至少需要n个箭头穿透所有区间：

只是有一点不一样，在intervalSchedule算法中，如果两个区间的边界触碰，不算重叠；而按照这道题目的描述，箭头如果碰到气球的边界气球也会爆炸，所以说相当于区间的边界触碰也算重叠：

所以只要将之前的算法稍作修改，就是这道题目的答案：

int findMinArrowShots(vector<interval> intvs) {
    // ...
    for (auto i : intvs) {
        // 把 >= 改成 > 就行了
        if (i.start > x_end) {
            count++;
            x_end = i.end;
        }
    }
    return count;
}

对于区间问题的处理，一般来说第一步都是排序，相当于预处理降低后续操作难度。