这是一个面试问题
有一家航空公司想要为其所有航班提供新的更新出席会议。每个空乘人员从一开始就有工作时间time
i (si)到结束时间i (ei)。设计一个最小化的算法公司必须召开的会议。
我的方法是选择结束时间最短的空乘人员。然后删除所有开始时间<=此结束时间的座席(因为他们已经知道会议的更新)。继续，直到没有乘务员可以选择。航空公司应该在我挑选的乘务员下班时间召开会议。
这是正确的方法吗?如果是，如何证明其正确性。
我认为复杂度是O (n log n)，因为我将首先按照结束时间的升序对列表进行排序，并遍历列表一次。
根据我的理解，所描述的算法通过以下参数产生最优解。确定一个实例及其最优解;固定工作周期最早结束时间t;如果一个会议安排在t-1，那么所有早于t开始的工作时间都可以由这个会议来服务，因此使用到t的多个会议的任何最优解决方案都可以得到改进。另一方面，在t-1时间之前必须至少有一次会议，否则一些工作期间将无法送达。
删除服务的工作时间后，我们得到了同样问题的一个较小的实例。通过迭代使用上述参数，可以获得最小会议次数。