70、Google 算法笔试题
有一台机器，上面有 m 个储存空间。然后有 n 个请求，第 i 个请求计算时需要占 R[i]个空
间，储存计算结果则需要占据 O[i]个空间（据 O[i]个空间（其中 O[i]<R[i]）。问怎么安排这 n
个请求的顺序，使得所有请求都能完成。你的算法也应该能够判断出无论如何都不能处理完
的情况。比方说，m=14，n=2，R[1]=10，O[1]=5，R[2]=8，O[2]=6。在这个例子中，我们
可以先运行第一个任务，剩余 9 个单位的空间足够执行第二个任务；但如果先走第二个任
务，第一个任务执行时空间就不够了，因为 10>14-6。
题解：
第i个请求计算时需要占 R[i]个空间，储存计算结果则需要占据O[i]个空间（其中 O[i]<R[i]）
假设可以满足所有请求，并且处理请求的顺序是:r1,r2,……r(n-1),r(n)，
那么存储完所有的请求结果后，剩余的存储空间为L=m-∑O[i]。
如果假设成立，必须满足：针对请求r(n)，一定有L+O[r(n)]>=R[r(n)]。
同理，针对r(n-1)，一定有L+O[r(n)]+O[r(n-1)]>=R[r(n-1)]，依次类推。
于是，证明假设成立就转化为：
针对假设中的每一个请求r(i)，都有L+∑O[r(n-j)]>=R[r(i)]，其中i>=j>=0。
相应的，原问题也就转化成从寻找这样的r(i)。
既然如此，从寻找r(n)开始，这时候有n个选择(R[1]~R[n])，
那么选择哪一个呢？如上所说，我们选择的原则是满足L+O[r(n)]>=R[r(n)]，
即L>=R[r(n)]-O[r(n)]。
所以将所有的选择按照R[r(n)]-O[r(n)]从小到大排序，每次选择时试探R[r(n)]-O[r(n)]最小的值，
如果最小值都不能满足，那么已经证明假设不成立，否则继续探测n-1，n-2……1，直到出现不能满足的情况，
或者证明假设成立。
时间复杂度：nlogn（事先的排序）+n