合作专线:17362615757

AI新闻

当前位置:首页 > 行业资讯 > AI新闻

一份贪心算法区间内统一调度其他问题多种解法详细攻略,抢走不郑

【导读】什么是贪心算法呢?贪心算法可以认为是动态规划算法的一个特例,相比动态规划,使用贪心算法需要满足更多的条件(贪心选择性质),但是效率比动态规划要高。比如说一个算法问题使用暴力解法需要指数级时间,如果能使用动态规划消除重叠子问题,就可以降到多项式级别的时间,如果满足贪心选择性质,那么可以进一步降低时间复杂度,达到线性级别的。什么是贪心选择性质呢,简单说就是:每一步都做出一个局部最优的选择,最终的结果就是全局最优。注意哦,这是一种特殊性质,其实只有一小部分问题拥有这个性质。比如你面前放着 100 张人民币,你只能拿十张,怎么才能拿最多的面额?显然每次选择剩下钞票中面值最大的一张,最后你的选择一定是最优的。然而,大部分问题都明显不具有贪心选择性质。比如打斗地主,对手出对儿三,按照贪心策略,你应该出尽可能小的牌刚好压制住对方,但现实情况我们甚至可能会出王炸。这种情况就不能用贪心算法,而得使用动态规划解决,参见前文 动态规划解决博弈问题。一、问题概述言归正传,本文解决一个很经典的贪心算法问题 Interval Scheduling(区间调度问题)。给你很多形如[start,end]的闭区间,请你设计一个算法,算出这些区间中最多有几个互不相交的区间。int intervalScheduling(int[][] ints) {}举个例子,intvs=[[1,3],[2,4],[3,6]],这些区间最多有两个区间互不相交,即[[1,3],[3,6]],你的算法应该返回 2。注意边界相同并不算相交。这个问题在生活中的应用广泛,比如你今天有好几个活动,每个活动都可以用区间[start,end]表示开始和结束的时间,请问你今天最多能参加几个活动呢?二、贪心解法这个问题有许多看起来不错的解决思路,实际上都不能得到正确答案。比如说:也许我们可以每次选择可选区间中开始最早的那个?但是可能存在某些区间开始很早,但是很长,使得我们错误地错过了一些短的区间。或者我们每次选择可选区间中最短的那个?或者选择出现冲突最少的那个区间?这些方案都能很容易举出反例,不是正确的方案。正确的思路其实很简单,可以分为以下三步:从区间集合 intvs 中选择一个区间 x,这个 x 是在当前所有区间中结束最早的(end 最小)。把所有与 x 区间相交的区间从区间集合 intvs 中删除。重复步骤 1 和 2,直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。把这个思路实现成算法的话,可以按每个区间的end数值升序排序,因为这样处理之后实现步骤 1 和步骤 2 都方便很多:现在来实现算法,对于步骤 1,由于我们预先按照end排了序,所以选择 x 是很容易的。关键在于,如何去除与 x 相交的区间,选择下一轮循环的 x 呢?由于我们事先排了序,不难发现所有与 x 相交的区间必然会与 x 的end相交;如果一个区间不想与 x 的end相交,它的start必须要大于(或等于)x 的end:下面看下代码:三、应用举例下面举例几道 LeetCode 题目应用一下区间调度算法。第 435 题,无重叠区间:我们已经会求最多有几个区间不会重叠了,那么剩下的不就是至少需要去除的区间吗?int eraseOverlapIntervals(int[][] intervals) { int n = intervals.length; return n - intervalSchedule(intervals);}第 452 题,用最少的箭头射爆气球:其实稍微思考一下,这个问题和区间调度算法一模一样!如果最多有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;}这么做的原因也不难理解,因为现在边界接触也算重叠,所以start == x_end时不能更新区间 x。本文终。对于区间问题的处理,一般来说第一步都是排序,相当于预处理降低后续操作难度。但是对于不同的问题,排序的方式可能不同,这个需要归纳总结,以后再写写这方面的文章。

长按识别二维码微信洽谈 免费发布信息推广
粤ICP备19111974号 深圳市织梦羊贸易有限公司 www.zmyang.com