区间调度问题：选择重叠最少任务的贪心策略正确性求证

你的策略无法保证得到最大化任务完成数的最优解，以下通过反例证明其错误性：

反例构造 #

假设有6个任务，时间区间如下：

• 任务1: [1, 100]（与其他所有5个任务重叠，重叠数5）
• 任务2: [2, 3]（与任务1、3重叠，重叠数2）
• 任务3: [4, 5]（与任务1、2、4重叠，重叠数3）
• 任务4: [6, 7]（与任务1、3、5重叠，重叠数3）
• 任务5: [8, 9]（与任务1、4重叠，重叠数2）
• 任务6: [10, 11]（仅与任务1重叠，重叠数1）

按你的策略执行 #

任务6的重叠数最少（仅1次），优先选择任务6后，需排除与之重叠的任务1。剩余任务为2、3、4、5，其中任务2与3重叠，3与4重叠，4与5重叠，最多只能选出2个不重叠任务（例如2+4或3+5），最终完成任务总数为 3个。

最优解执行 #

放弃重叠最少的任务6，选择任务2、3、4、5：这四个任务彼此之间无重叠，可全部完成，最终完成任务总数为 4个，明显优于你的策略结果。

为什么最早完成时间策略有效 #

最早完成时间的贪心策略核心是：每一步选择最早结束的任务，能最大化剩余的可用时间区间，从而为后续任务留出更多空间。这一策略的正确性可通过交换论证证明：假设存在最优解未采用该策略，我们可以将最优解中的第一个任务替换为最早完成的任务，得到的解仍为最优解，递归可得整个策略的正确性。

内容的提问来源于stack exchange，提问作者Martin