algorithm - 优化:最小化 session 次数

Question

这是一道面试题

There is an airline company that wants to provide new updates to all of its flight attendants through meetings. Each ith flight attendant has a working time from start time i (si) to end time i (ei). Design an algorithm that minimizes the number of meetings that company has to hold.

我的做法是挑一个结束时间最小的空姐。然后删除所有开始时间 <= 这个结束时间的出席者(因为他们已经知道 session 的更新)。继续，直到没有空乘人员可供选择。航空公司应该在我挑选的那些服务员的结束时间举行 session 。

这是正确的做法吗？如果是，如何证明其正确性。

我认为复杂度是 O (n log n)，因为我将首先按结束时间的升序对列表进行排序，然后遍历一次列表。

Answer 1

据我了解，所描述的算法通过以下参数产生了一个最优解。修复一个实例及其最优解；固定一个工作周期的最早结束时间t；如果 session 安排在 t-1，则所有早于 t 开始的工作时段都可以由该 session 提供服务，因此使用多于一个 session 的任何最佳解决方案直到 t 可以改进。另一方面，在 t-1 之前必须至少有一次 session ，否则某些工作时段将无法服务。

删除服务工作时间后，我们获得了相同问题的较小实例。通过迭代使用上述参数，获得最小 session 次数。