用於合併會議計劃的設計數據結構

Question

我被要求爲會議計劃設計數據結構，然後再合併它們。例如，如果人A從上午9:00到上午10:00開會，而人B從上午9:30到上午11:30開會，則合併的忙時隙從上午9:00到上午11:30。

我爲Person創建了類，而這個類擁有會議對象的集合。 Meeting類的開始時間爲[24小時制]，因此我可以輕鬆進行比較。

class Person { 
String name; 
Collection<Meeting> meetings; 

} 


class Meeting{ 
int hh, mm; 
int duration; // duration will be in minutes from where we can get the end time. 
} 

我想知道哪個數據結構對於合併最有效。 一種方法是使用會議的排序ArrayList。

任何更好的設計表示讚賞。

Answer 1

由於@Anonymouse建議您可以使用96位即12個字節來表示一天，因此從凌晨1點開始的30分鐘會議將表示爲110000，您可以使用簡單|對所有號碼進行操作。

時間O（n）內存O（12n）字節。理論上這將更快。

---

給定會議[分鐘開始時間，分鐘結束時間]。

合併兩個會議（薩& Sb）的入鈧重疊時

鈧[最小值（SA-開始，SB-開始），最大（SA-端，SB-端）]，並存儲在收集合並的會議。如果不重疊，則可以將它們分開存儲。

我們知道，在一天內總分鐘數= 24 * 60 = 1440 如果你有15個分單位則變成24 *十五分之六十零= 96（下1個字節）

因此，你需要每2個字節時間表，即字節開始，結束。

時間爲O（n）內存O（2N）字節

---

，如果您有以後刪除會議兩個辦法都不行。爲此，您一定要分開保存所有原始會議日程。

Answer 2

由於安排小於15分鐘的時段會議是不現實的，因此我會爲... long解決。每天64位，足夠16小時;我不需要那麼多。如果你願意的話，也可以使用兩個longs /三個整數整天。

然後合併爲|操作。對於更大的時間片，我可以移動 - 或者他們，然後檢查未設置位作爲會議開始時間。這個高度壓縮的數據結構只會因爲低級別的操作而觸發任何索引。 CPU緩存可以適應數百天/用戶的時間表。

Answer 3

這是Task Scheduling的經典問題。