algorithm - 间隔调度问题：按最晚开始时间的顺序接受请求总是最优的？

Question

我了解到，当我们按照最早完成时间的顺序接受请求时，间隔调度问题是最优的。

那么，如果我们按照最晚开始时间的顺序接受请求，我们是否也总是有最优解呢？

我认为这是错误的，因为我们会得到一个不同的时间表，但我想知道我怎样才能提出一个更数学的证明。

标签： algorithmgreedy

Answer 1

按最晚开始时间排程同：

1. 反向时间（否定所有时间并且交换间隔结束）
2. 按最早完成时间安排
3. 再次倒转时间以恢复原始间隔。

通过对称性，无论您是否反转时间，可调度间隔的最大数量都是相同的，因此如果“最早完成时间”是最优的，那么“最晚开始时间”也是最优的。