一道google笔试题

脑袋锈掉了，不能看书，于是只能在网上瞎转。

在Matrix67的blog看到一个面试题，由于直接看了其解法，没怎么思考，于是想着如何证明一下其解法正确。

题目如下：

说有一台机器，上面有m个储存空间。然后有n个请求，第i个请求计算时需要占R[i]个空间，储存计算结果则需要占据O[i]个空间（其中O[i]14-6。

看完第一个例子后首先想到按Oi从小到大的顺序来做。但举个例子可以证明这样不行：R1=10,O1=4,R2=13,O2=5, m=15。若按Oi顺序，先1再2，明显不行。先2再1倒是可以。

按照Matrix所提解法，按R与O之差从大到小的顺序来做。下面来证明其正确性。

首先定义松弛时间Li = Ri - Oi。

假设Li >  Lj，当前空间为FS。我们来证明按松弛时间从大到小来调度的最优性，即如果先 i 后 j 都不能调度的话，反过来肯定不能调度。

假如先 i 后 j 不能调度，即 Oi + Rj > FS

由Li > Lj，得 Ri - Oi > Rj - Oj, <===> Oj + Ri > Oi + Rj > FS

而  Oj + Ri 为先 j 后 i 调度顺序所需的空间，它大于FS，可见这种顺序肯定不能调度。QED。