和之前的两道course schedule不同，这道题和图一点关系也没有。是interval类的题，一般很大可能跟贪婪有关系。这道题要我们schedule course从而可以完成最多的课程，对完成的定义是，这个course要在它的deadline之前完成。我们知道每个课程的长度t和deadline d，我们要决定如何选择这些课程。首先我们假设所有input都是合理的，也就是d >= t，否则这个课程是没法schedule的。那么既然更deadline有关，我们假设先选deadline更早的。但是显然这样没法达到最优解，比如(5,5), (2,6),(4,6)，我们先选第一个，但是事实上最优解是选后面两个。那么我们需要修改我们的算法，如果没有空间放了，并且我们发现之前所选的集合中有比当前课程i更长的课程j我们把课程j换出来，把课程i换入集合。这样我们可以让集合的总时间T更短，可以给之后的课程更多的空间，并且也满足条件，因为i的deadline比j的deadline还要晚，我们总时间反而缩短，代表课程i的结束时间（总课程时间）比j在的时候总课程的结束时间还要早，所以仍然满足条件。如何证明这个算法正确性呢。我们在这篇文章中提到过如何证明贪婪算法的正确性，这里我们第二种思路证明。
假设存在解S，C代表所有课程的集合，dd[i]表示课程i的deadline，t[i]代表课程i的长度，假设我们存在一个pair (i, j)，dd[j] >= dd[i]并且t[j] <= t[i]，把课程i从S的集合换出 把j换入，我们之前证明过依然满足条件，但是这样可以让总时间T缩短。换句话说，给定集合S的大小，我们每remove一个这样的pair，总时间T就会减小，翻过来，每多一个这样的pair总时间T增加，所以当不存在这样的pair时，T是最小的。也就是当最优解O和S的size是一样的话，S的总时间总是小于等于O的，那么如果O之后可以容纳更多的课程，S同理也应该容纳同样多的课程，所以O的size不可能大于S，所以S就是最优解。
为了记录当前S中持续时间最长的课程，我们需要优先队列，时间复杂度O(nlogn)，代码如下：
这道题还有另外一种变体，如果我们不是求最多可以上的课程。而是假设我们有n个task，每个task有持续时间和deadline，每一个task如果有delay，delay的时间为完成时间f(i) - dd[i]，那么如何schedule task使得总的delay时间最少。这里直觉告诉我们是EDF(earliest deadline first)，那么这个算法的正确性，我们需要进一步证明，我们依然采取第二种思路证明。假设解S种存在pair(i, j)，f[i] < f[j]并且dd[i] > dd[j]，如图所示：
假设我们交换一对pair，首先job j的delay减少了。那么对于job i来说delay增加但是总的delay有没有减少呢？假设交换前job j完成时间为T。交换前job j的delay为T - dd[j]，交换后job i的delay为T - dd[i]，但是dd[i] > dd[j]所以job i的delay增加了但依然比交换前job j的delay要少，并且交换后job j的delay也减少了，所以总的delay减少。也就是每remove这样一个pair，我们的总delay会减少，那么清楚所有这样的pair之后，delay就是最小的。代码略过，就是简单的按deadline排序。
那么我们从这里也可以看出一道题greedy算法通常是凭直觉来推断出来的，然后再去试图证明这个算法的正确性。一般不可能将这个过程反过来，因为实在是太不好想了。
No comments:
Post a Comment