什么是贪?算法呢？ 贪?算法可以认为是动态规划算法的?个特例， 相?动态规划， 使?贪?算法需要满?更多的条件（贪?选择性质） ， 但是效率?动态规划要?。
?如说?个算法问题使?暴?解法需要指数级时间， 如果能使?动态规划消除重叠?问题， 就可以降到多项式级别的时间， 如果满?贪?选择性质， 那么可以进?步降低时间复杂度， 达到线性级别的。
什么是贪?选择性质呢， 简单说就是： 每?步都做出?个局部最优的选择，最终的结果就是全局最优。 注意哦， 这是?种特殊性质， 其实只有?部分问题拥有这个性质。
?如你?前放着 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题，?最少的箭头射爆?球：
查看：数据结构与算法 ，查看完整技术文档和完整的数据结构算法视频教程资料，包含左神算法全部系列。