多机调度问题 - 贪心算法详解及证明

多机调度问题是指将一批任务分配到多个机器上，使得所有任务完成时间最短。贪心算法是一种常用的求解多机调度问题的方法，其基本思路是每次选择最优的任务进行分配。

具体实现步骤如下：

1. 将所有任务按照完成时间从小到大排序。
2. 初始化每个机器的完成时间为0。
3. 从第一个任务开始，将其分配到完成时间最早的机器上，并更新该机器的完成时间。
4. 对于后续的每个任务，选择完成时间最早的机器进行分配，并更新该机器的完成时间。
5. 循环执行步骤4，直到所有任务都被分配完毕。

贪心算法的正确性可以通过反证法证明。假设存在一个最优解与贪心算法得到的解不同，那么一定存在至少一个任务在两种解中被分配到不同的机器上。设这个任务在最优解中被分配到机器i上，在贪心算法中被分配到机器j上。由于最优解的完成时间最短，所以机器i的完成时间一定比机器j的完成时间早。而贪心算法是每次选择完成时间最早的机器进行分配，所以不存在其他机器的完成时间比机器i更早。因此，贪心算法得到的解是最优解之一，与假设矛盾。

总之，贪心算法是一种简单有效的求解多机调度问题的方法，其时间复杂度为O(nlogn)，其中n为任务数量。