4.18 如何判断请求能否在给定的存储条件下完成
【出自BD笔试题】
难度系数：★★★☆☆ 被考察系数：★★★★☆
题目描述：
给定一台有m个存储空间的机器，有n个请求需要在这台机器上运行，第i个请求计算时需要占R[i]空间，计算结果需要占O[i]个空间（O[i]＜R[i]）。请设计一个算法，判断这n个请求能否全部完成？若能，给出这n个请求的安排顺序。
分析与解答：
这道题的主要思路是：首先对请求按照R[i]-O[i]由大到小进行排序，然后按照由大到小的顺序进行处理，如果按照这个顺序能处理完，则这n个请求能被处理完，否则处理不完。那么请求i能完成的条件是什么呢？在处理请求i的时候前面所有的请求都已经处理完成，那么它们所占的存储空间为O（0）+O（1）+…+O（i-1），那么剩余的存储空间left为left=m-（O（0）+O（1）+…+O（i-1）），要使请求i能被处理，则必须满足left＞=R[i]，只要剩余的存储空间能存放的下R[i]，那么在请求处理完成后就可以删除请求，从而把处理的结果放到存储空间中。由于O[i]＜R[i]，此时必定有空间存放O[i]。
至于为什么用R[i]-O[i]由大到小的顺序来处理，请看下面的分析：
假设第一步处理R[i]-O[i]最大的值。使用归纳法（假设每一步都取剩余请求中R[i]-O[i]最大的值进行处理），假设n=k时能处理完成，那么当n=k+1时，由于前k个请求是按照R[i]-O[i]从大到小排序的，在处理第k+1个请求时，此时需要的空间为A=O[1]+…+O[i]+…+O[k]+R[k+1]，只有A＜=m的时候才能处理第k+1个请求。假设把第k+1个请求和前面的某个请求i换换位置，即不按照R[i]-O[i]由大到小的顺序来处理，在这种情况下，第k+1个请求已经被处理完成，接着要处理第i个请求，此时需要的空间为B=O[1]+…+O[i-1]+O[k+1]+O[i+1]+…+R[i]，如果B＞A，则说明按顺序处理成功的可能性更大（越往后处理剩余的空间越小，请求需要的空间越小越好）；如果B＜A，则说明不按顺序更好。根据R[i]-O[i]有序的特点可知：R[i]-O[i]＞=R[k+1]-O[k+1]，即O[k+1]+R[i]＞=O[i]+R[k+1]，所以，B＞=A，因此，可以得出结论：方案B不会比方案A更好。即方案A是最好的方案，也就是说，按照R[i]-O[i]从大到小排序处理请求，成功的可能性最大。如果按照这个序列都无法完成请求序列，那么任何顺序都无法实现全部完成，实现代码如下：
程序的运行结果如下：
按照如下请求序列可以完成：
20，423，810，215，716，86，59，87，6
算法性能分析：
这种方法的时间复杂度为O（N^2）。