你有N个人。每个人都有一个空闲时间段列表。
例如，人 1 的空闲时间段可能是 [(9, 9.5); (11, 12.5)] 这意味着他在 9 到 9:30 和 11:00 到 12:30 之间有空。
您想找到一个时间段，以便将所有 N 个人聚集在一起并开会 2 小时。
写一个方法:
输入:
a list of list, each list inside is the free time period list of a person
输出:
one or more time period that you can use to have the N persons meeting for 2 hours; or you cannot find such a time period
我的想法是这样的:
按以下方式合并两个人的时间段列表:如果两个时间段不重叠，则删除开始时间较早的那个；否则，将重叠部分(新时间段)放入新列表并删除开始时间较早的部分。继续合并。
合并完成后，我们得到一个新的两个人时间重叠的列表，然后将它与第三个人合并，以此类推，直到所有列表都合并。
扫描最终合并列表并找出 2 小时时段。
如果假设每个人有 M 个空闲时间段，则此算法是 **O(N*M)。
有没有更好的解决方案？
最佳答案
您的输入大小为 N*M，因此您无法获得更好的时间复杂度 - 您必须读取所有输入。
最初我误读了问题并在下面发布了算法；它的时间复杂度仅略大于输入大小 (O(nm log nm))，但可以解决更一般的情况，当您希望在无法满足所有人的情况下最大程度地增加 session 人数时一次。
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.
关于algorithm - 这个调度算法有更好的解决方案吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22037617/