今天我又干牛B事情了……听说三教有Google的实习生招聘笔试，再想到传说中Google笔试里的牛题，我毫不犹豫地就杀去了。说实话，我倒真没想认真做题，只是过去看一看传说中的Google笔试题是什么样子的。由于我什么都没准备，连事前是否要报名都不知道，因此呢，与其说是“处女笔”，倒不如说是一次“霸王笔”。BBS上说要带简历和成绩单，于是打印了一份巨牛无比的“简历”和很不像话的成绩单。
考试时间19:00-20:30，来自各个学校的人几乎坐满了整整一层楼的教室。两个挂着工作牌的MM进来，给每个人发了一张质量巨好的草稿纸和一个用来把试卷、简历、成绩单固定在一起的曲别针。试卷很厚一叠。选择题很简单。编程题没看（最讨厌在纸上写代码了）。算法题很有意思，和大家分享一下。
说有一台机器，上面有m个储存空间。然后有n个请求，第i个请求计算时需要占R[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。
这个题到底该怎么整呢？我当时花了全部的时间去想各种网络流、费用流、图的分层思想等等，最后写了一个铁定错误的贪心上去。直到考试结束4个小时以后我才想到了正确算法的——只需要按照R值和O值之差（即释放空间的大小）从大到小排序，然后依次做就是了……
来自：http://www.matrix67.com/blog/archives/1714
相关文章
