📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 1303| 回复: 7
跳转到指定楼层
上一主题 下一主题
收起左侧

[其他] 问一道区间的高频题

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
n个时间段,让你计算最多多少段时间相互不重叠,证明算法正确性?

评分

参与人数 2大米 +4 收起 理由
ytx2013 + 2 很有用的信息!
14417335 + 2

查看全部评分


上一篇:亚麻老七题,到底是什么?
下一篇:Python这样处理数组算不算in place?
🔗
红A 2021-1-15 02:35:48 | 只看该作者
全局:
backtracking + dp?记得以前面经有过一道类似的,greedy是不行的。
回复

使用道具 举报

🔗
shurui91 2021-1-15 06:24:21 | 只看该作者
全局:
红A 发表于 2021-1-15 02:35
backtracking + dp?记得以前面经有过一道类似的,greedy是不行的。

greedy的题有一些确实比较恶心 局部最优并不导致整体最优 证明greedy不行 有例子最好了
回复

使用道具 举报

🔗
han6 2021-1-15 06:40:44 | 只看该作者
全局:
排序,然后假设最后一个区间是1号,那么有多少个不重复的;假设最后一个区间是2号,那么有多少个不重复的;...;假设最后一个区间是n号,那么有多少个不重复的。最后找出最大值。
回复

使用道具 举报

🔗
红A 2021-1-15 06:55:47 | 只看该作者
全局:
shurui91 发表于 2021-1-15 06:24
greedy的题有一些确实比较恶心 局部最优并不导致整体最优 证明greedy不行 有例子最好了

我记得之前mock或者是面经?被搞过这道题,然后我出greedy对方给了反例。

----- ----- ------
   -----  -----

类似这样全部都一样长,please correct me if I am wrong. 太久远了记不清了。
回复

使用道具 举报

🔗
julie19 2021-1-15 08:51:42 | 只看该作者
全局:
挺像这道题的?
https://leetcode.com/problems/merge-intervals/
可以再开一个数组记录区间是不是被修改过。然后数多少个没有被修改过。

感觉很straightforward不用证明,所以什么叫证明算法的正确性?
回复

使用道具 举报

🔗
ytx2013 2021-1-15 10:03:07 | 只看该作者
全局:
感觉是 lis 的变形, 把每个区间看成是“变胖”了的数, double-size
回复

使用道具 举报

🔗
magicsets 2021-1-15 14:08:46 | 只看该作者
全局:
本帖最后由 magicsets 于 2021-1-15 14:10 编辑

这个问题叫做interval scheduling (maximization) problem,其实经常作为贪心算法的例子出现在算法课程上。

比如下面这些课程notes都讲解了这个问题:
(1) https://homes.cs.washington.edu/ ... 06/Lecture06_07.pdf
(2) http://www.cs.ust.hk/mjg_lib/Cla ... ctures/09greedy.pdf
(3) http://www.cs.toronto.edu/~lalla/373s16/notes/ISP.pdf
(4) https://people.cs.umass.edu/~sheldon/teaching/cs312/lec/lec08.pdf
(5) https://www.cs.umd.edu/class/fal ... 07-greedy-sched.pdf

而使用的贪心算法叫做Earliest Finish time First (EFF) ,就是将所有区间按照finish time(也就是右端点)从小到大排序,然后维护一个区间集合R,依次对于排序后的每一个区间I,如果I与S中已有的区间没有交集则将I加入到R中。

至于正确性证明则是比较有意思的部分,贪心算法的证明往往都相当深刻地揭示了问题本身的结构,并不是那么容易想出来的而是需要一定的学术训练。不过这个区间调度问题的证明很简洁 —— 这也是很多算法课程使用它当例子的原因。

证明的思路简单来说是这样的。给定任意输入S,假设使用上述贪心算法给出的解(不妨称为EFF)选择的区间序列是S[i_1], S[i_2], ..., S[i_k],而最优解(不妨称为OPT)为S[j_1], S[j_2], ..., S[j_m] —— 注意这里OPT里各个j具体是啥我们其实不用管(因为输入S有无穷种可能),而是利用数学归纳法的方法来处理无穷性,从而证明可以通过一系列区间替换使得OPT可以在区间数量不变的不变性下可以在有限步内等价到EFF,从而证明EFF也是最优的。

具体的证明过程可以看上面任一个notes,比如HKUST的写得不错而且只有两页slides:http://www.cs.ust.hk/mjg_lib/Cla ... ctures/09greedy.pdf

评分

参与人数 2大米 +11 收起 理由
不知道小帅 + 3 给你点个赞!
14417335 + 8

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表