数据结构算法之贪心算法，贪心算法之区间调度问题
什么是贪⼼算法呢？ 贪⼼算法可以认为是动态规划算法的⼀个特例， 相⽐动态规划， 使⽤贪⼼算法需要满⾜更多的条件（贪⼼选择性质） ， 但是效率⽐动态规划要⾼。
⽐如说⼀个算法问题使⽤暴⼒解法需要指数级时间， 如果能使⽤动态规划消除重叠⼦问题， 就可以降到多项式级别的时间， 如果满⾜贪⼼选择性质， 那么可以进⼀步降低时间复杂度， 达到线性级别的。
什么是贪⼼选择性质呢， 简单说就是： 每⼀步都做出⼀个局部最优的选择，最终的结果就是全局最优。 注意哦， 这是⼀种特殊性质， 其实只有⼀部分问题拥有这个性质。
⽐如你⾯前放着 100 张⼈⺠币， 你只能拿⼗张， 怎么才能拿最多的⾯额？ 显然每次选择剩下钞票中⾯值最⼤的⼀张， 最后你的选择⼀定是最优的。
然⽽， ⼤部分问题明显不具有贪⼼选择性质。 ⽐如打⽃地主， 对⼿出对⼉三， 按照贪⼼策略， 你应该出尽可能⼩的牌刚好压制住对⽅， 但现实情况我们甚⾄可能会出王炸。 这种情况就不能⽤贪⼼算法， ⽽得使⽤动态规划解决， 参⻅前⽂「动态规划解决博弈问题」 。
⼀、 问题概述
⾔归正传， 本⽂解决⼀个很经典的贪⼼算法问题 Interval Scheduling（区间调度问题） 。 给你很多形如 [start, end] 的闭区间， 请你设计⼀个算法，算出这些区间中最多有⼏个互不相交的区间。
int intervalSchedule(int[][] intvs) {}
举个例⼦， intvs = [[1,3], [2,4], [3,6]] ， 这些区间最多有 2 个区间互不相交， 即 [[1,3], [3,6]] ， 你的算法应该返回 2。 注意边界相同并不算相交。
这个问题在⽣活中的应⽤⼴泛， ⽐如你今天有好⼏个活动， 每个活动都可以⽤区间 [start, end] 表⽰开始和结束的时间， 请问你今天最多能参加⼏个活动呢？ 显然你⼀个⼈不能同时参加两个活动， 所以说这个问题就是求这些时间区间的最⼤不相交⼦集。
⼆、 贪⼼解法
这个问题有许多看起来不错的贪⼼思路， 却都不能得到正确答案。 ⽐如说：也许我们可以每次选择可选区间中开始最早的那个？ 但是可能存在某些区间开始很早， 但是很⻓， 使得我们错误地错过了⼀些短的区间。 或者我们每次选择可选区间中最短的那个？ 或者选择出现冲突最少的那个区间？ 这些⽅案都能很容易举出反例， 不是正确的⽅案。
正确的思路其实很简单， 可以分为以下三步：
-
从区间集合 intvs 中选择⼀个区间 x， 这个 x 是在当前所有区间中结束最早的（end 最⼩） 。
-
把所有与 x 区间相交的区间从区间集合 intvs 中删除。
-
重复步骤 1 和 2， 直到 intvs 为空为⽌。 之前选出的那些 x 就是最⼤不相交⼦集。
把这个思路实现成算法的话， 可以按每个区间的 end 数值升序排序， 因为这样处理之后实现步骤 1 和步骤 2 都⽅便很多:
【PDF格式⽆法显⽰GIF⽂件 interval/1.gif， 可移步点击数据结构算法 访问学习】
现在来实现算法， 对于步骤 1， 由于我们预先按照 end 排了序， 所以选择x 是很容易的。 关键在于， 如何去除与 x 相交的区间， 选择下⼀轮循环的 x呢？
由于我们事先排了序， 不难发现所有与 x 相交的区间必然会与 x 的 end 相交； 如果⼀个区间不想与 x 的 end 相交， 它的 start 必须要⼤于（或等于） x 的 end ：
三、代码实现
public int intervalSchedule(int[][] intvs) {
if (intvs.length == 0) return 0;
// 按 end 升序排序
Arrays.sort(intvs, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[1] - b[1];
}
});
// ⾄少有⼀个区间不相交
int count = 1;
// 排序后， 第⼀个区间就是 x
int x_end = intvs[0][1];
for (int[] interval : intvs) {
int start = interval[0];
if (start >= x_end) {
// 找到下⼀个选择的区间了
count++;
x_end = interval[1];
}
}
returncount;
}
四、应⽤举例
下⾯举例⼏道LeetCode题⽬应⽤⼀下区间调度算法。第435题，⽆重叠区间：
我们已经会求最多有⼏个区间不会重叠了，那么剩下的不就是⾄少需要去除的区间吗？
interaseOverlapIntervals(int[][]intervals){
intn=intervals.length;
returnn-intervalSchedule(intervals);
}
第452题，⽤最少的箭头射爆⽓球：
查看：数据结构与算法 ，查看完整技术文档和完整的数据结构算法视频教程资料，包含左神算法全部系列。