所有時間間隔的最大重疊數

給定一組時間間隔，如何找到最大重疊數no。有沒有任何算法可以解決時間複雜度爲O（n log n）或O（n）？的給定問題？例如：（6：00-9：30），（9：00-12：30），（10：00-10：30），（12：00-14：30），（11:00）（12：00-14：30） -13：30）。答案是3所有時間間隔的最大重疊數

來源

2013-08-21 user2601967

這取決於。如果一個項目重疊兩個不同的集合，它被認爲是一個重疊或兩個重疊？另外，（12:14:30）是正確的嗎？它是時間戳嗎？鑑於其他集合，這只是不一致的。 – Firo

是否有4次重疊？假設（12:14:30）應該是（12：00-14：30） –

@Firo這是一個錯字，請參閱編輯後的版本。 – user2601967

使用快速排序 - O(nlogn)時間對值排序。

6:00(+) 
9:30(-) 
9:00(+) 
12:30(-) 
10:00(+) 
10:30(-) 
12:14:30(Dude wut?) --> Im going to assume you meant 12:00(+) ,14:30(-) 
11:00(+) 
13:30(-)

變爲

6:00(+) 
9:00(+) 
9:30(-) 
10:00(+) 
10:30(-) 
11:00(+) 
12:00(+) 
12:30(-) 
13:30(-) 
14:30(-)

迭代通過列表遞增，每加和遞減，每減，記錄發現的最大值。這需要O(n)時間

總時間O(nlogn + n) = O(nlogn)

來源

2013-08-21 18:43:11 gbtimmon

@ gbtimmon，這是驚人的人！謝謝 – user2601967

所有時間間隔的最大重疊數

回答

相關問題