返回信息流问题如下：
一层楼沿着走廊南北向的两边各有200个房间。最近，公司要做一次装修，需要在各个办公室之间搬运办公桌。由于走廊狭窄，办公桌都很大，走廊里一次只能通过一张办公桌。必须制定计划提高搬运效率。经理制定如下计划：一张办公桌从一个房间移到另一个房间最多用十分钟。当从房间i移动一张办公桌到房间j，两个办公室之间的走廊都会被占用。所以，每10分钟内，只要不是同一段走廊，都可以在房间之间移动办公桌。
这个问题的常见解法是贪心，建立一个200长度的int数组，初始化为0，然后对每一个移动所覆盖的数组区域计数+1，最后以数组的最大值为解
假设最大值是M，即M个10分钟可以移动完毕，我们能看出小于M显然不行，但是不代表M一定可以
而且这里的贪心解法也不能给出具体的移动策略，所以希望能有大神给出一个比较严谨的证明。。
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #91960同步于 2017/2/19
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】一道贪心问题的证明
Mrsuyi
2017/2/19镜像同步1 回复
订阅后，新回复会通过你的通知中心匿名送达。
1 条回复
好吧我自己证出来了。。。
通过以下步骤可以得到一个具体的移动执行策略
1.把每一个移动用一个pair {a, b} (a < b)表示，然后把这些pair按a从小到大排列，命名为sorted
2.每一个移动回合开始之后，我们不断地从sorted里面挑靠前（first最小）且不与本回合已有的移动重叠的pair加入到本回合中
3.如果没有可以添加的pair了，而且sorted不为空，那么就开启一个新的回合，然后继续步骤2
举个栗子
假设数组长度为4 => [1, 2, 3, 4]，需要的移动是[1, 2] [2, 3] [3, 4]
第一次操作添加[1, 2]到回合1
第二次操作添加[3, 4]到回合1
第三次操作添加[2, 3]到回合2
最后结果如图
1, 2, 3, 4
==== ==== 第一回合
==== 第二回合
假设我们对于某一个输入按如上的算法得出了一个解决方案，这个方案需要M个回合。
我们考虑第M个回合的第一个pair的a所覆盖的那个房间，那个房间在之前的所有回合一定都被某个移动所覆盖。因为如果不是这样，这个pair早就应该在之前的某个回合中被选进去了，这和我们的操作步骤是矛盾的，所以这种情况不会发生。所以这个房间在M个回合内都是被占用的。所以少于M个回合的解决方案是不存在的。而且多于M次占用的房间也是不存在的，否则我们不可能得出一个M回合的解决方案。所以这个M和我们贪心得出的最大覆盖数是一致的，也就证明了贪心策略是正确的