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

以前看FB的面经见到过这样一道题：任务调度。给出一个数组，里面的每个数字代表着一个任务的标号。在允许重新排列任务和插入空闲时间片段（一个片段

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

还有一种贪婪做法可以达到O(n)（具体见  的25楼），但我没办法严格证明它的正确性。请问各位有什么看法吗？

zhuhai_ZFC 发表于 2016-9-12 22:37
哦。我也说嘛。因为这种情况下其实是可以不插空排好的：1,2,3,4,1,2,3,4,5,1,2,3,4,5。
其实我想知道贪 ...

我知道怎么证了……一定可以构造无缝插入的……

知道最多的标号m1和个数n1，就知道下界肯定是(interval+1) * (n1 - 1)
这时候，和刚才的做法一样，每个m1和身后的interval个间隔为一组，把m2, m3, ...mk往里塞
当然原来的空槽每组只能塞interval个

但是，当所有空闲塞满了以后，我们只需要在组与组的中间继续塞，一定能够满足条件，因为每组的长度是不减的，所以不会造成冲突。

所以可以用那个方法算。

他的贪婪算法应该是错的。
对于[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:
[1, 1, 1, 2, 2, 3], interval = 2
step1: [1 _ _ 1 _ _ 1]
step2: [1 2 _ 1 2 _ 1]
step3: [1 2 3 1 2 _ 1]

example2:
[1, 1, 1, 1, 2, 2, 3, 3, 4, 4] interval = 3
step1: [1 _ _ _ 1 _ _ _ 1 _ _ _ 1]
step2: [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]

显然由于第二多的标号m2数量n2必定不多于n1，那么必然不会增加时间，以此类推。

如此，即使有interval个数量为n1的标号，也不会增加时间

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

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

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

这个确实不太好说，但是总体思路就是这样。

南慕伦 发表于 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。所以你那个例子里面，还是会返回数列长度，也就是正确结果。

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:29
那就[1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 5, _, _ ,_ 5]  interval = 3

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

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

南慕伦 发表于 2016-9-12 22:34
卧槽，这是贪心算法的反例，证明错了。

补充内容 (2016-9-12 22:35):

哦。我也说嘛。因为这种情况下其实是可以不插空排好的：1,2,3,4,1,2,3,4,5,1,2,3,4,5。
其实我想知道贪婪算法的正确性怎么证明。因为我觉得贪婪算法应该是对的。

我理解楼主的顾虑。
就是说即使【待插入元素数量】<=【剩余空位数量】，为什么一定能插进去。

有一个点要注意，贪心的插入方式是，
从频率最高的task开始，找当前task没有使用过的interval中，空位最多的interval

比如目前有如下空位
_ _ | _ _ | _ _
我还需要插task，以及task的频率。
B:2
C:2
D:2

这样插入B之后，毫无悬念:
B _ | B _ | _ _

C如何插入呢？
是这样的：
B _ | B _ | C _
B C | B _ | C _

这样的插法，每一步插入完成之后，
能保证【有空位的interval数量】>= 【当前待插元素的最大频率】
问题就是怎么证明这个特性

就发现这就变成一个数学证明题了。

所以我觉得楼主链接的那个答案，虽然用的是正确的结论，不过onsite最好不要写。
代码量太少，又无法彻底证明，面试官不认可就惨了。

不如就用LC358中逐个interval填充的办法，代码量在那里摆着，面试官也不会找茬。