這個調度算法的更好的解決方案？

Question

你有N個人。每個人都有一段空閒時間段。

例如，Person 1的空閒時間段可能是[（9,9.5）; （11,12.5）]，這意味着他在9點到9點半和11點到12點半之間是免費的。

您想找到一個時間段，以便您可以將所有N人聚集在一起並召開2小時的會議。

寫一個方法：

輸入：

列表的列表，每個列表內是 人的空閒時間週期列表

輸出：

一個或多個時間段，您可以使用N個人會議 2小時;或者你不能找到這樣一個時間段

---

什麼，我想是這樣的：

• 合併兩個人的時間段列出了以下方法：如果兩個時間段沒有按」 t重疊，然後刪除具有較早開始時間的那個;否則，將重疊部分（新時間段）放到新列表中，並刪除具有較早開始時間的部分。繼續合併。

• 合併完成後，我們會得到一個新的列表，其中包含兩個人的時間重疊，然後將其與第三個人合併，直到所有列表合併爲止。

• 掃描最終的合併列表並找出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.