Skip to content

Latest commit

 

History

History
313 lines (235 loc) · 11.3 KB

贪心算法之区间调度问题.md

File metadata and controls

313 lines (235 loc) · 11.3 KB

贪心算法之区间调度问题

GitHub

《labuladong 的算法秘籍》、《labuladong 的刷题笔记》两本 PDF 和刷题插件 2.0 免费开放下载,详情见 labuladong 的刷题三件套正式发布~

读完本文,你不仅学会了算法套路,还可以顺便去 LeetCode 上拿下如下题目:

435. 无重叠区间

452.用最少数量的箭引爆气球

-----------

什么是贪心算法呢?贪心算法可以认为是动态规划算法的一个特例,相比动态规划,使用贪心算法需要满足更多的条件(贪心选择性质),但是效率比动态规划要高。

比如说一个算法问题使用暴力解法需要指数级时间,如果能使用动态规划消除重叠子问题,就可以降到多项式级别的时间,如果满足贪心选择性质,那么可以进一步降低时间复杂度,达到线性级别的。

什么是贪心选择性质呢,简单说就是:每一步都做出一个局部最优的选择,最终的结果就是全局最优。注意哦,这是一种特殊性质,其实只有一部分问题拥有这个性质。

比如你面前放着 100 张人民币,你只能拿十张,怎么才能拿最多的面额?显然每次选择剩下钞票中面值最大的一张,最后你的选择一定是最优的。

然而,大部分问题明显不具有贪心选择性质。比如打斗地主,对手出对儿三,按照贪心策略,你应该出尽可能小的牌刚好压制住对方,但现实情况我们甚至可能会出王炸。这种情况就不能用贪心算法,而得使用动态规划解决,参见前文「动态规划解决博弈问题」。

一、问题概述

言归正传,本文解决一个很经典的贪心算法问题 Interval Scheduling(区间调度问题)。给你很多形如 [start, end] 的闭区间,请你设计一个算法,算出这些区间中最多有几个互不相交的区间

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 都方便很多:

1

现在来实现算法,对于步骤 1,由于我们预先按照 end 排了序,所以选择 x 是很容易的。关键在于,如何去除与 x 相交的区间,选择下一轮循环的 x 呢?

由于我们事先排了序,不难发现所有与 x 相交的区间必然会与 x 的 end 相交;如果一个区间不想与 x 的 end 相交,它的 start 必须要大于(或等于)x 的 end

2

看下代码:

public int intervalSchedule(int[][] intvs) {
    if (intvs.length == 0) return 0;
    // 按 end 升序排序
    Arrays.sort(intvs, new Comparator<int[]>() {
        @Override
        public int compare(int[] a, int[] b) {
            // 这里不能使用 a[1] - b[1],要注意溢出问题
            if (a[1] < b[1])
                return -1;
            else if (a[1] > b[1])
                return 1;
            else return 0;
        }
    });
    // 至少有一个区间不相交
    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;
}

三、应用举例

下面举例几道 LeetCode 题目应用一下区间调度算法。

第 435 题,无重叠区间:

title1

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

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

第 452 题,用最少的箭头射爆气球:

title2

其实稍微思考一下,这个问题和区间调度算法一模一样!如果最多有 n 个不重叠的区间,那么就至少需要 n 个箭头穿透所有区间:

3

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

4

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

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

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

_____________

刷算法,学套路,认准 labuladong,公众号和 在线电子书 持续更新最新文章

本小抄即将出版,微信扫码关注公众号,后台回复「小抄」限时免费获取,回复「进群」可进刷题群一起刷题,带你搞定 LeetCode

======其他语言代码======

435. 无重叠区间

452.用最少数量的箭引爆气球

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