目标: 找出相互兼容的工作的最大子集

 

 

 

 

 

 

 

     “贪婪模式“。逐个考虑工作。接受这一项工作，只要它与已经接受的工作相容。

　　　　[最早开始时间] 按sj的升序考虑工作。

 

　　　　[最早完成时间] 按fj的升序考虑工作。

 

　　　　[最短区间]        按fj - sj的升序考虑。

 

　　　　[冲突最少]         对于每个工作j，计算有冲突的工作cj的数量。按cj的升序进行调度。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 　　设贪心不是最优的，我们看看会发生什么。

 

　　设i1, i2，…ik表示贪婪选择的作业集。

 

　　令j1, j2，…jm表示最优解i1 = j1, i2 = j2，对于r的最大可能值，ir = jr。