贪心算法之区间调度问题
通知:数据结构精品课 和 递归算法专题课 限时附赠网站会员,全新纸质书《labuladong 的算法笔记》 出版,签名版限时半价!另外,建议你在我的 网站 学习文章,体验更好。
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
435. Non-overlapping Intervals | 435. 无重叠区间 | 🟠 |
452. Minimum Number of Arrows to Burst Balloons | 452. 用最少数量的箭引爆气球 | 🟠 |
-----------
什么是贪心算法呢?贪心算法可以认为是动态规划算法的一个特例,相比动态规划,使用贪心算法需要满足更多的条件(贪心选择性质),但是效率比动态规划要高。
比如说一个算法问题使用暴力解法需要指数级时间,如果能使用动态规划消除重叠子问题,就可以降到多项式级别的时间,如果满足贪心选择性质,那么可以进一步降低时间复杂度,达到线性级别的。
什么是贪心选择性质呢,简单说就是:每一步都做出一个局部最优的选择,最终的结果就是全局最优。注意哦,这是一种特殊性质,其实只有一部分问题拥有这个性质。
比如你面前放着 100 张人民币,你只能拿十张,怎么才能拿最多的面额?显然每次选择剩下钞票中面值最大的一张,最后你的选择一定是最优的。
然而,大部分问题明显不具有贪心选择性质。比如打斗地主,对手出对儿三,按照贪心策略,你应该出尽可能小的牌刚好压制住对方,但现实情况我们甚至可能会出王炸。这种情况就不能用贪心算法,而得使用动态规划解决,参见前文 动态规划解决博弈问题。
一、问题概述
言归正传,本文解决一个很经典的贪心算法问题 Interval Scheduling(区间调度问题),也就是力扣第 435 题「无重叠区间」:
给你很多形如 [start, end]
的闭区间,请你设计一个算法,算出这些区间中最多有几个互不相交的区间。
int intervalSchedule(int[][] intvs);
举个例子,intvs = [[1,3], [2,4], [3,6]]
,这些区间最多有 2 个区间互不相交,即 [[1,3], [3,6]]
,你的算法应该返回 2。注意边界相同并不算相交。
这个问题在生活中的应用广泛,比如你今天有好几个活动,每个活动都可以用区间 [start, end]
表示开始和结束的时间,请问你今天最多能参加几个活动呢?显然你一个人不能同时参加两个活动,所以说这个问题就是求这些时间区间的最大不相交子集。
_____________
本文为会员内容,请扫码关注公众号或 点这里 查看:
====其他语言代码====
python
Edwenc 提供 第435题的python3 代码:
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
### 思路是首先找到不重叠的区间的个数
### 然后再用总个数减去不重叠个数
### 获得的就是 需要移除的个数
# 首先获得区间的个数 为0的话就不用移除
n = len(intervals)
if n==0:
return 0
# 按照每个区间的右端点值进行排序
sorted_list = sorted( intervals , key=lambda x: x[1] )
# 不重叠区间个数至少是1
count = 1
# end是所有不重叠的区间中 最大的右端点
# end的初始值即是sorted_list[0]的右端点
end = sorted_list[0][1]
# 从1开始往后找 因为0在上面已经取过了
for i in range(1,n):
# start是当前区间左端点值
start = sorted_list[i][0]
# 如果当前左端点比最大右端点都大了(可能相等)
# 说明两区间不重叠 count+1 再更新end
if start>=end:
count += 1
end = sorted_list[i][1]
# 最后返回的是 需要移除的区间个数
return n-count
javascript
区间调度实现
var intervalSchedule = function (intvs) {
if (intvs.length === 0) return 0;
// 按end升序排序
intvs.sort((a, b) => {
if (a[1] < b[1])
return -1;
else if (a[1] > b[1])
return 1;
else return 0;
})
// 至少有一个区间不相交
let count = 1;
// 排序后,第一个区间就是 x
let x_end = intvs[0][1];
for (let interval of intvs) {
let start = interval[0];
if (start >= x_end) {
// 找到下一个选择的区间了
count++;
x_end = interval[1];
}
}
return count;
}
第435题 无重叠区间
/**
* @param {number[][]} intervals
* @return {number}
*/
var eraseOverlapIntervals = function (intervals) {
let n = intervals.length;
// 我们已经会求最多有几个区间不会重叠了,那么剩下的不就是至少需要去除的区间吗?
return n - intervalSchedule(intervals);
};
var intervalSchedule = function (intvs) {
if (intvs.length === 0) return 0;
// 按end升序排序
intvs.sort((a, b) => {
if (a[1] < b[1])
return -1;
else if (a[1] > b[1])
return 1;
else return 0;
})
// 至少有一个区间不相交
let count = 1;
// 排序后,第一个区间就是 x
let x_end = intvs[0][1];
for (let interval of intvs) {
let start = interval[0];
if (start >= x_end) {
// 找到下一个选择的区间了
count++;
x_end = interval[1];
}
}
return count;
}
第452题 用最少数量的箭引爆气球
/**
* @param {number[][]} points
* @return {number}
*/
var findMinArrowShots = function (intvs) {
if (intvs.length === 0) return 0;
// 按end升序排序
intvs.sort((a, b) => {
if (a[1] < b[1])
return -1;
else if (a[1] > b[1])
return 1;
else return 0;
})
// 至少有一个区间不相交
let count = 1;
// 排序后,第一个区间就是 x
let x_end = intvs[0][1];
for (let interval of intvs) {
let start = interval[0];
if (start > x_end) {
// 找到下一个选择的区间了
count++;
x_end = interval[1];
}
}
return count;
};