任务 j j j开始时间为 s j s_j sj，终止时间为 f j f_j fj，任务 j j j所在时间段即为 [ s j , f j ] [s_j,f_j] [sj,fj]。若两个任务所在时间段不重叠，则称两个任务兼容。求最大互不兼容的任务子集。
①按照开始时间从早到晚排序，若该任务与之前任务都兼容，则选取该任务，若不兼容则不选取该任务并查看下一个任务，知道所有任务都被检查一遍结束。反例如下： 上述策略得到最大子集大小为1，实际最大子集大小为4
②按照时间间隔从小到大排序，若该任务与之前任务都兼容，则选取该任务，若不兼容则不选取该任务并查看下一个任务，知道所有任务都被检查一遍结束。反例如下： 上述策略得到最大子集大小为1，实际最大子集大小为2
③按照与自身冲突的任务数量由小到大进行排序，若该任务与之前任务都兼容，则选取该任务，若不兼容则不选取该任务并查看下一个任务，知道所有任务都被检查一遍结束。反例如下： 与6号块冲突的块数量为2，与1、4号块冲突的块个数为3，其余块的冲突个数为4。上述策略得到最大子集大小为3(1、6、4)，实际最大子集大小为4（1、2、3、4）
按照结束时间由早到晚排序，或者按照开始时间由晚到早排序，若该任务与之前任务都兼容，则选取该任务，若不兼容则不选取该任务并查看下一个任务，知道所有任务都被检查一遍结束。 我们对结束时间由早到晚排序为贪心策略进行证明 反证法： 我们假设按照以上贪心策略得到的不是最优解，且令 i 1 , i 2 , … , i k i_1,i_2,\dots,i_k i1,i2,…,ik表示由贪心策略选出的任务；令 j 1 , j 2 , … , j m j_1,j_2,\dots,j_m j1,j2,…,jm表示最优解中的任务，我们不妨设最优解中最多存在r个任务与贪心解中的任务相同，即 i 1 = j 1 , i 2 = j 2 , … , i r = j r i_1= j_1,i_2= j_2,\dots,i_r= j_r i1=j1,i2=j2,…,ir=jr,得到结果如下图所示： 其中由于贪心策略，任务 i r + 1 i_{r+1} ir+1的结束时间早于任务 j r + 1 j_{r+1} jr+1，并且由于最优解中任务数一定大于贪心解任务数( m > k m>k m>k)，所以任务 j r + 1 j_{r+1} jr+1一定存在。此时我们可以在不改变最优解性质的情况下，用任务 i r + 1 i_{r+1} ir+1替换任务 j r + 1 j_{r+1} jr+1，如下图： 此时最优解中存在r+1个任务与贪心解中的任务一致，与我们之前假设的最多存在r个任务与贪心解中的任务相同矛盾，连续推证可得，贪心解与最优解中所有任务相同，即贪心解为最优解，以上贪心策略得到的解是最优解。
