一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 931|回复: 6
收起左侧

求fb经典面经的答案与证明-任务调度

[复制链接] |试试Instant~ |关注本帖
zhuhai_ZFC 发表于 2016-9-12 13:06:58 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 其他@Facebook - Other - 其他 |Other其他

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
以前看FB的面经见到过这样一道题:任务调度。给出一个数组,里面的每个数字代表着一个任务的标号。在允许重新排列任务和插入空闲时间片段(一个片段等于一个任务时间)的情况下,标号相同的任务之间需要至少间隔k个任务。求完成所有任务的最短时间。我看到网上有用堆做的,有直接用贪婪算法做的。想请教一下,有没有谁能给出一个严格证明, 证明这些算法是正确的?我比较认可用堆的方法,因为我感觉这道题和LC358很像,而LC358的正确性我是知道怎么证明的。这两题都是要在每个时刻选择剩余次数最多的那一项。只是LC358在没得选的情况下就返回false,而这道题没得选就插入空闲时间片。但是这个算法的时间复杂度就超过O(n)了。而还有一种贪婪做法可以达到O(n)(具体见 http://www.1point3acres.com/bbs/thread-161904-2-1.html 的25楼),但我没办法严格证明它的正确性。请问各位有什么看法吗?
南慕伦 发表于 2016-9-12 22:43:40 | 显示全部楼层
zhuhai_ZFC 发表于 2016-9-12 22:37
哦。我也说嘛。因为这种情况下其实是可以不插空排好的:1,2,3,4,1,2,3,4,5,1,2,3,4,5。
其实我想知道贪 ...

我知道怎么证了……一定可以构造无缝插入的……. 鍥磋鎴戜滑@1point 3 acres

知道最多的标号m1和个数n1,就知道下界肯定是(interval+1) * (n1 - 1)
这时候,和刚才的做法一样,每个m1和身后的interval个间隔为一组,把m2, m3, ...mk往里塞. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
当然原来的空槽每组只能塞interval个

但是,当所有空闲塞满了以后,我们只需要在组与组的中间继续塞,一定能够满足条件,因为每组的长度是不减的,所以不会造成冲突。. 1point3acres.com/bbs
.鐣欏璁哄潧-涓浜-涓夊垎鍦
所以可以用那个方法算。
回复 支持 1 反对 0

使用道具 举报

南慕伦 发表于 2016-9-12 14:46:46 | 显示全部楼层
他的贪婪算法应该是错的。
对于[1,2,3,4,1,2,3,4,1,2,3,4]这样的任务,(max-1)*(interval+1)+countOfMax
你取interval = 0 和 interval = 3 计算结果会不一样,但实际上这样安排已经最优 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

堆的方法是对的,和LC358差不多。大致的证明思路是,同样的组合,其它的放法一定不会比当前的放法更好。

证明的最重要一个思想就是,尽可能少增加空闲,完全无缝的安排一定是最优的。如果有空闲,就证明别的方法一定不会产生更少的空闲。

首先,对于数量最多那个标号m1,数量为n1,那么区间至少为(n1-1)*(interval+1) + 1
这时候,m1两两分割出长度为interval的空槽,将剩下的依次填放:
比如说
example 1:. 鍥磋鎴戜滑@1point 3 acres
[1, 1, 1, 2, 2, 3], interval = 2. more info on 1point3acres.com
step1: [1 _ _ 1 _ _ 1]
step2: [1 2 _ 1 2 _ 1]-google 1point3acres
step3: [1 2 3 1 2 _ 1]-google 1point3acres

example2:
[1, 1, 1, 1, 2, 2, 3, 3, 4, 4] interval = 3
step1: [1 _ _ _ 1 _ _ _ 1 _ _ _ 1]
. From 1point 3acres bbsstep2: [1 2 _ _ 1 2 _ _ 1 _ _ _ 1]
step3: [1 2 _ _ 1 2 _ _ 1 3 _ _ 1] --回头填-> [1 2 3 _ 1 2 _ _ 1 3 _ _ 1]
step4: [1 2 3 4 1 2 4 _ 1 3 _ _ 1]
.1point3acres缃
显然由于第二多的标号m2数量n2必定不多于n1,那么必然不会增加时间,以此类推。
. 1point 3acres 璁哄潧
如此,即使有interval个数量为n1的标号,也不会增加时间

那么,在前m1分割出的这几个区间被塞满之前,这样的塞法必定不会增加长度,而且由于m1是数量最多的,所以这是长度的下界,不可能比这更短。

下面来考虑区间被塞满的时候的情况。

这时候,最后塞进去的数字,比方说是m_k,必定是塞到最后一个m1前一个槽,那么这时候,有两种情况:
1、m_k 已经塞完。我们刚才已经证明之前那个长度是最短长度,并且没有增加长度,且之后的m_(k+1), m_(k+2), ... 不管怎么塞,都不会与前面冲突,所以如果后面那段最优,则仍然能够保证最优。而后面那段如果还用这样的塞法,则证明过程相同。
2、m_k 还没塞完,这个证明就比较复杂。这时候又分两种情况:. more info on 1point3acres.com
i) m_k剩余个数比剩下标号的剩余个数最多的标号个数少。这个比较好证明,因为可以根据那个个数计算出需要增加的长度下界。由于我们是之前所有的m个数都比当前的m_k多,所以,如果把m_k换到前面去放,一定不会得到更好的结果(因为换过来溢出的个数会相同或者更多),然后继续这样塞
ii) m_k剩余个数比剩下标号的剩余个数最多的标号个数多。这时候,同样可以求得需要增加的下界,同时,在增加的下界前所有空闲区间被塞满之前,不会再需要往后增加长度,也就是说可以有一个无缝安排。

这个确实不太好说,但是总体思路就是这样。
回复 支持 1 反对 0

使用道具 举报

 楼主| zhuhai_ZFC 发表于 2016-9-12 21:57:35 | 显示全部楼层
南慕伦 发表于 2016-9-12 14:46
他的贪婪算法应该是错的。
对于[1,2,3,4,1,2,3,4,1,2,3,4]这样的任务,(max-1)*(interval+1)+countOfMax
...

很牛的证明!不过我还是更更想知道贪婪算法有什么证明,或者有什么反例。因为你那个反例好像不太对。他的算法里,如果(max-1)*(interval+1)+countOfMax比nums.length小,那么就返回nums.length。所以你那个例子里面,还是会返回数列长度,也就是正确结果。
回复 支持 反对

使用道具 举报

南慕伦 发表于 2016-9-12 22:29:30 | 显示全部楼层
zhuhai_ZFC 发表于 2016-9-12 21:57
很牛的证明!不过我还是更更想知道贪婪算法有什么证明,或者有什么反例。因为你那个反例好像不太对。他的 ...

那就[1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 5, _, _ ,_ 5]  interval = 3
回复 支持 反对

使用道具 举报

南慕伦 发表于 2016-9-12 22:34:58 | 显示全部楼层
南慕伦 发表于 2016-9-12 22:29
那就[1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 5, _, _ ,_ 5]  interval = 3

卧槽,这是贪心算法的反例,证明错了。

补充内容 (2016-9-12 22:35):
*这是那个heap算法的反例……我的证明是错的。
回复 支持 反对

使用道具 举报

 楼主| zhuhai_ZFC 发表于 2016-9-12 22:37:36 | 显示全部楼层
南慕伦 发表于 2016-9-12 22:34
卧槽,这是贪心算法的反例,证明错了。

补充内容 (2016-9-12 22:35):
.1point3acres缃
哦。我也说嘛。因为这种情况下其实是可以不插空排好的:1,2,3,4,1,2,3,4,5,1,2,3,4,5。
其实我想知道贪婪算法的正确性怎么证明。因为我觉得贪婪算法应该是对的。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 13:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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