贪心算法之区间调度问题

数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

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);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int intervalSchedule(vector<vector<int>>& intvs);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def intervalSchedule(intvs: List[List[int]]) -> int:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func intervalSchedule(intvs [][]int) int

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var intervalSchedule = function(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 所示：

现在来实现算法，对于步骤 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];
        }
    }
    return count;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 定义函数，接收一个二维数组 intvs
int intervalSchedule(vector<vector<int>>& intvs) {
    // 如果 intvs 为空，则返回 0
    if (intvs.size() == 0) return 0;
    // 按照 intvs 数组中每个元素的第二个值进行升序排序
    sort(intvs.begin(), intvs.end(), [](vector<int>& a, vector<int>& b){
        return a[1] < b[1];
    });
    // 记录区间的数量最小为 1
    int count = 1;
    // 记录当前区间的结束时间
    int x_end = intvs[0][1];
    // 遍历 intvs 数组
    for (vector<int>& interval : intvs) {
        // 记录当前区间的开始时间
        int start = interval[0];
        // 如果当前区间的开始时间大于等于当前区间的结束时间，则表示当前区间可以选择
        if (start >= x_end) {
            count++; // 区间数量加 1
            x_end = interval[1]; // 记录当前区间的结束时间
        }
    }
    return count; // 返回区间数量
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List
def intervalSchedule(intvs: List[List[int]]) -> int:
    if len(intvs) == 0:
        return 0
    # 按 end 升序排序
    intvs.sort(key=lambda x: x[1])
    # 至少有一个区间不相交
    count = 1
    # 排序后，第一个区间就是 x
    x_end = intvs[0][1]
    for interval in intvs:
        start = interval[0]
        if start >= x_end:
            # 找到下一个选择的区间了
            count += 1
            x_end = interval[1]
    return count

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func intervalSchedule(intvs [][]int) int {
    if len(intvs) == 0 {
        return 0
    }
    // 按 end 升序排序
    sort.Slice(intvs, func(i, j int) bool {
        return intvs[i][1] < intvs[j][1]
    })
    // 至少有一个区间不相交
    count := 1
    // 排序后，第一个区间就是 x
    x_end := intvs[0][1]
    for _, interval := range intvs {
        start := interval[0]
        if start >= x_end {
            // 找到下一个选择的区间了
            count++
            x_end = interval[1]
        }
    }
    return count
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var intervalSchedule = function(intvs) {
    if (intvs.length === 0) return 0;
    // 按 end 升序排序
    intvs.sort(function(a, b) {
        return a[1] - b[1];
    });
    // 至少有一个区间不相交
    var count = 1;
    // 排序后，第一个区间就是 x
    var x_end = intvs[0][1];
    for (var i = 0; i < intvs.length; i++) {
        var start = intvs[i][0];
        if (start >= x_end) {
            // 找到下一个选择的区间了
            count++;
            x_end = intvs[i][1];
        }
    }
    return count;
};

三、应用举例

下面再举例几道具体的题目应用一下区间调度算法。

首先是力扣第 435 题「 无重叠区间」问题：

输入一个区间的集合，请你计算，要想使其中的区间都互不重叠，至少需要移除几个区间？函数签名如下：

int eraseOverlapIntervals(int[][] intvs);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int eraseOverlapIntervals(vector<vector<int>>& intvs);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def eraseOverlapIntervals(intvs: List[List[int]]) -> int

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func eraseOverlapIntervals(intvs [][]int) int

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var eraseOverlapIntervals = function(intvs) {}

其中，可以假设输入的区间的终点总是大于起点，另外边界相等的区间只算接触，但并不算相互重叠。

比如说输入是 intvs = [[1,2],[2,3],[3,4],[1,3]]，算法返回 1，因为只要移除 [1,3] 后，剩下的区间就没有重叠了。

我们已经会求最多有几个区间不会重叠了，那么剩下的不就是至少需要去除的区间吗？

int eraseOverlapIntervals(int[][] intervals) {
    int n = intervals.length;
    return n - intervalSchedule(intervals);
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    int n = intervals.size();
    return n - intervalSchedule(intervals);
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
    n = len(intervals)
    return n - intervalSchedule(intervals)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func eraseOverlapIntervals(intervals [][]int) int {
    n := len(intervals)
    return n - intervalSchedule(intervals)
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var eraseOverlapIntervals = function(intervals) {
    var n = intervals.length;
    return n - intervalSchedule(intervals);
};

再说说力扣第 452 题「 用最少的箭头射爆气球」，我来描述一下题目：

假设在二维平面上有很多圆形的气球，这些圆形投影到 x 轴上会形成一个个区间对吧。那么给你输入这些区间，你沿着 x 轴前进，可以垂直向上射箭，请问你至少要射几箭才能把这些气球全部射爆呢？

函数签名如下：

int findMinArrowShots(int[][] intvs);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int findMinArrowShots(vector<vector<int>>& intvs);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def findMinArrowShots(intvs: List[List[int]]) -> int:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func findMinArrowShots(intvs [][]int) int

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var findMinArrowShots = function(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 个箭头穿透所有区间：

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

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

int findMinArrowShots(int[][] intvs) {
    // ...

    for (int[] interval : intvs) {
        int start = interval[0];
        // 把 >= 改成 > 就行了
        if (start > x_end) {
            count++;
            x_end = interval[1];
        }
    }
    return count;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int findMinArrowShots(vector<vector<int>>& intvs) {
    // ...

    for (vector<int>& interval : intvs) {
        int start = interval[0];
        // 把 >= 改成 > 就行了
        if (start > x_end) {
            count++;
            x_end = interval[1];
        }
    }
    return count;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def findMinArrowShots(intvs: List[List[int]]) -> int:
    # ...

    for interval in intvs:
        start = interval[0]
        # 把 >= 改成 > 就行了
        if start > x_end:
            count += 1
            x_end = interval[1]
    return count

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func findMinArrowShots(intvs [][]int) int {
    // ...

    for _, interval := range intvs {
        start := interval[0]
        // 把 >= 改成 > 就行了
        if start > x_end {
            count++
            x_end = interval[1]
        }
    }
    return count
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var findMinArrowShots = function(intvs) {
    // ...

    for (var i = 0; i < intvs.length; i++) {
        var interval = intvs[i];
        var start = interval[0];
        // 把 >= 改成 > 就行了
        if (start > x_end) {
            count++;
            x_end = interval[1];
        }
    }
    return count;
};

接下来可阅读：

引用本文的文章

＿＿＿＿＿＿＿＿＿＿＿＿＿

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释