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

Question

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

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

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

Answer 1

按最晚开始时间安排与：

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

根据对称性，无论你是否倒转时间，可调度间隔的最大数量都是相同的，所以如果“最早完成时间”是最优的，那么“最晚开始时间”也是最优的。

Answer 2

作为提示，想象一下所有时间间隔的镜像，或者假装时间倒流。你知道贪婪的“取最早的结束时间”会 select 最大间隔数。如果时间向后扫，等价条件是什么？