关于这个算法的正确性的证明：
首先，我们可以看到好多人的解决方法是给每个路径都加上一个计数器，最后这么多计数器的最大值就是结果，但计数器的最大值只是结果的下限，我们还必须说明存在一个解能达到这个下限，这个解必然就是最优解了。
为了证明这个贪心算法正确，我们可以证明：在计数器的最大值为N时，经过一轮贪心选互不相交区间操作之后，计数器的最大值为N-1。
1、所有在这一轮被选走的区间（即在这一轮移动玩的桌子）上的计数器的值必然减1。
2、其他区间上的计数器值不变，但其他区间上的计数器的值一定小于N。
假设第一轮移走的连续两个桌子占用走廊区间为[a1,a2],[b1,b2]，我们要证明区间（a2,b1）上的所有计数器的值全部都小于N，不妨考察a2+1处的计数器值。
假设a2+1处的计数器值为N，则由于搬桌子时采取了贪心策略，且搬完桌子[a1,a2]之后，直接搬走了桌子[b1,b2]，所有覆盖了a2+1的桌子并未被移动，因此覆盖a2+1处的N个桌子的区间的开始位置必然小于a2，即覆盖了a2+1的N张桌子必然同时覆盖a2。同时考虑到a2处已经被搬走了一张桌子，因此在这次搬桌子之前，a2处计数器的值为N+1，与假设矛盾！因此a2+1处的计数器的值必然小于N，同理，(a2,b1)区间上的所有计数器的值全都小于N。
证明完成！
搬了一轮桌子后，计数器最大值就必然减1，因此最多搬N次桌子，所有计数器值为0，即搬完了。
同时，由于计数器最大值为N，意味着我们至少要搬N次，所以用此贪心算法达到的搬N次是最优结果。
亦即次贪心算法正确！
证明完成！

• Re:此题使用贪心算法正确性的证明 (709) 422245257 2019-08-30 19:04:20