---
title: '贪心算法之区间调度问题'
---
![](https://labuladong.github.io/pictures/souyisou1.png)
**通知:[数据结构精品课](https://aep.h5.xeknow.com/s/1XJHEO) 已更新到 V2.1,[手把手刷二叉树系列课程](https://aep.xet.tech/s/3YGcq3) 上线。[第 18 期每日打卡](https://aep.xet.tech/s/2PLO1n) 开始报名。另外,建议你在我的 [网站](https://labuladong.github.io/algo/) 学习文章,体验更好。**
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
| LeetCode | 力扣 | 难度 |
| :----: | :----: | :----: |
| [435. Non-overlapping Intervals](https://leetcode.com/problems/non-overlapping-intervals/) | [435. 无重叠区间](https://leetcode.cn/problems/non-overlapping-intervals/) | 🟠
| [452. Minimum Number of Arrows to Burst Balloons](https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/) | [452. 用最少数量的箭引爆气球](https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/) | 🟠
**-----------**
什么是贪心算法呢?贪心算法可以认为是动态规划算法的一个特例,相比动态规划,使用贪心算法需要满足更多的条件(贪心选择性质),但是效率比动态规划要高。
比如说一个算法问题使用暴力解法需要指数级时间,如果能使用动态规划消除重叠子问题,就可以降到多项式级别的时间,如果满足贪心选择性质,那么可以进一步降低时间复杂度,达到线性级别的。
什么是贪心选择性质呢,简单说就是:每一步都做出一个局部最优的选择,最终的结果就是全局最优。注意哦,这是一种特殊性质,其实只有一部分问题拥有这个性质。
比如你面前放着 100 张人民币,你只能拿十张,怎么才能拿最多的面额?显然每次选择剩下钞票中面值最大的一张,最后你的选择一定是最优的。
然而,大部分问题明显不具有贪心选择性质。比如打斗地主,对手出对儿三,按照贪心策略,你应该出尽可能小的牌刚好压制住对方,但现实情况我们甚至可能会出王炸。这种情况就不能用贪心算法,而得使用动态规划解决,参见前文 [动态规划解决博弈问题](https://labuladong.github.io/article/fname.html?fname=动态规划之博弈问题)。
### 一、问题概述
言归正传,本文解决一个很经典的贪心算法问题 Interval Scheduling(区间调度问题),也就是力扣第 435 题「无重叠区间」:
给你很多形如 `[start, end]` 的闭区间,请你设计一个算法,**算出这些区间中最多有几个互不相交的区间**。
```java
int intervalSchedule(int[][] intvs);
```
举个例子,`intvs = [[1,3], [2,4], [3,6]]`,这些区间最多有 2 个区间互不相交,即 `[[1,3], [3,6]]`,你的算法应该返回 2。注意边界相同并不算相交。
这个问题在生活中的应用广泛,比如你今天有好几个活动,每个活动都可以用区间 `[start, end]` 表示开始和结束的时间,请问你今天**最多能参加几个活动呢**?显然你一个人不能同时参加两个活动,所以说这个问题就是求这些时间区间的最大不相交子集。
### 二、贪心解法
这个问题有许多看起来不错的贪心思路,却都不能得到正确答案。比如说:
也许我们可以每次选择可选区间中开始最早的那个?但是可能存在某些区间开始很早,但是很长,使得我们错误地错过了一些短的区间。或者我们每次选择可选区间中最短的那个?或者选择出现冲突最少的那个区间?这些方案都能很容易举出反例,不是正确的方案。
正确的思路其实很简单,可以分为以下三步:
1、从区间集合 `intvs` 中选择一个区间 `x`,这个 `x` 是在当前所有区间中**结束最早的**(`end` 最小)。
2、把所有与 `x` 区间相交的区间从区间集合 `intvs` 中删除。
3、重复步骤 1 和 2,直到 `intvs` 为空为止。之前选出的那些 `x` 就是最大不相交子集。
把这个思路实现成算法的话,可以按每个区间的 `end` 数值升序排序,因为这样处理之后实现步骤 1 和步骤 2 都方便很多,如下 GIF 所示:
![](https://labuladong.github.io/pictures/interval/1.gif)
现在来实现算法,对于步骤 1,由于我们预先按照 `end` 排了序,所以选择 `x` 是很容易的。关键在于,如何去除与 `x` 相交的区间,选择下一轮循环的 `x` 呢?
**由于我们事先排了序**,不难发现所有与 `x` 相交的区间必然会与 `x` 的 `end` 相交;如果一个区间不想与 `x` 的 `end` 相交,它的 `start` 必须要大于(或等于)`x` 的 `end`:
![](https://labuladong.github.io/pictures/interval/2.jpg)
看下代码:
```java
public int intervalSchedule(int[][] intvs) {
if (intvs.length == 0) return 0;
// 按 end 升序排序
Arrays.sort(intvs, new Comparator() {
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];
}
}
return count;
}
```
### 三、应用举例
下面再举例几道具体的题目应用一下区间调度算法。
首先是力扣第 435 题「无重叠区间」问题:
输入一个区间的集合,请你计算,要想使其中的区间都互不重叠,至少需要移除几个区间?函数签名如下:
```java
int eraseOverlapIntervals(int[][] intvs);
```
其中,可以假设输入的区间的终点总是大于起点,另外边界相等的区间只算接触,但并不算相互重叠。
比如说输入是 `intvs = [[1,2],[2,3],[3,4],[1,3]]`,算法返回 1,因为只要移除 `[1,3]` 后,剩下的区间就没有重叠了。
我们已经会求最多有几个区间不会重叠了,那么剩下的不就是至少需要去除的区间吗?
```java
int eraseOverlapIntervals(int[][] intervals) {
int n = intervals.length;
return n - intervalSchedule(intervals);
}
```
再说说力扣第 452 题「用最少的箭头射爆气球」,我来描述一下题目:
假设在二维平面上有很多圆形的气球,这些圆形投影到 x 轴上会形成一个个区间对吧。那么给你输入这些区间,你沿着 x 轴前进,可以垂直向上射箭,请问你至少要射几箭才能把这些气球全部射爆呢?
函数签名如下:
```java
int findMinArrowShots(int[][] intvs);
```
比如说输入为 `[[10,16],[2,8],[1,6],[7,12]]`,算法应该返回 2,因为我们可以在 `x` 为 6 的地方射一箭,射爆 `[2,8]` 和 `[1,6]` 两个气球,然后在 `x` 为 10,11 或 12 的地方射一箭,射爆 `[10,16]` 和 `[7,12]` 两个气球。
其实稍微思考一下,这个问题和区间调度算法一模一样!如果最多有 `n` 个不重叠的区间,那么就至少需要 `n` 个箭头穿透所有区间:
![](https://labuladong.github.io/pictures/interval/3.jpg)
只是有一点不一样,在 `intervalSchedule` 算法中,如果两个区间的边界触碰,不算重叠;而按照这道题目的描述,箭头如果碰到气球的边界气球也会爆炸,所以说相当于区间的边界触碰也算重叠:
![](https://labuladong.github.io/pictures/interval/4.jpg)
所以只要将之前的算法稍作修改,就是这道题目的答案:
```java
int findMinArrowShots(int[][] intvs) {
// ...
for (int[] interval : intvs) {
int start = interval[0];
// 把 >= 改成 > 就行了
if (start > x_end) {
count++;
x_end = interval[1];
}
}
return count;
}
```
接下来可阅读:
* [贪心算法之跳跃游戏](https://labuladong.github.io/article/fname.html?fname=跳跃游戏)
引用本文的文章
- [一个方法解决三道区间问题](https://labuladong.github.io/article/fname.html?fname=区间问题合集)
- [分治算法详解:运算优先级](https://labuladong.github.io/article/fname.html?fname=分治算法)
- [剪视频剪出一个贪心算法](https://labuladong.github.io/article/fname.html?fname=剪视频)
- [如何运用贪心思想玩跳跃游戏](https://labuladong.github.io/article/fname.html?fname=跳跃游戏)
- [扫描线技巧:安排会议室](https://labuladong.github.io/article/fname.html?fname=安排会议室)
**_____________**
**《labuladong 的算法小抄》已经出版,关注公众号查看详情;后台回复关键词「**进群**」可加入算法群;回复「**全家桶**」可下载配套 PDF 和刷题全家桶**:
![](https://labuladong.github.io/pictures/souyisou2.png)
======其他语言代码======
[435. 无重叠区间](https://leetcode-cn.com/problems/non-overlapping-intervals/)
[452.用最少数量的箭引爆气球](https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons)
### python
Edwenc 提供 第435题的python3 代码:
```python
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
**区间调度实现**
```js
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题 无重叠区间**
```js
/**
* @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题 用最少数量的箭引爆气球**
```js
/**
* @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;
};
```