这个调度算法有什么更好的解决方案吗？

Question

你有N个人。每个人都有一个空闲时间段的列表。

例如，人1的自由时间可能是(9，9.5)；(11，12.5)，这意味着他在9:30和11:00到12:30之间自由。

你想找一个时间段，这样你就可以把所有的N个人聚集在一起，并有一个2小时的会议。

编写一种方法：

投入：

一个列表，里面的每个列表都是一个人的空闲时间段列表。

产出：

一段或多段时间，你可以用来让N个人开会2小时；或者你找不到这样一个时间段。

我想的是这样的：

• 将两人的时间段列表合并如下:如果两个时间段不重叠，则删除具有早期启动时间的时间段；否则，将重叠部分(一个新时间段)放到新列表中，并删除具有早期启动时间的部分。继续合并。
• 合并完成后，我们得到一个新的列表，它与两个人的时间重叠，然后与第三个人合并，等等，直到所有的列表被合并。
• 扫描最终合并列表，并找出2小时插槽。

该算法是**O(N*M)，假设每个人都有M空闲时间段。

有更好的解决方案吗？

Answer 1

您的输入具有N*M的大小，因此您无法获得更好的时间复杂度-您必须读取所有的输入。

最初，我误解了这个问题，并在下面发布了算法；它的时间复杂度仅略大于输入大小(O(nm log nm))，但是解决了更一般的情况，如果您想要最大化会议上的人数，如果他们不能一次见面的话。

1. Merge periods (a, b), (b, c) into (a, c)
2. Forget periods shorter than 2 hours
3. Transform your input into list of 
    (timestamp_of_beginning, person_id, True)
    (timestamp_of_ending - 2 hours, person_id, False)
4. Sort the list by first element of tuple
5. Iterate over the list, with a set A, 
   adding person_id to A on (_, person_id, True),
   and removing on (_, person_id, False). 

   If after processing some item (t, _, _) 
   A has k elements, you can have a meeting of k persons, their ids are in A.

6. The maximal size of A during iteration is the maximal number of persons 
   that can have the meeting.