會議調度程序算法。段樹的情況？

公司可供會議使用的會議室數量爲n個。您需要預訂特定時段的會議。寫一個算法來確定在給定的開始時間和結束時間內可用於會議的會議室的數量。會議調度程序算法。段樹的情況？

提示：將選擇任何會議室與非重疊會議。

我想段樹能提供這個O（logN）的，但不知道這就是每個查詢的最佳方法

來源

2016-05-19 Pinhead

你能分享一下你的實現（代碼）嗎？ –

是，O（logn）時間是最佳的。

如果您必須安排所有會議，您可以將所有開始時間和結束時間放入一個向量中，對它們進行排序，然後遍歷排序的向量並分配會議室。仍然O（NlogN）由於排序，但常數較小，內存訪問模式應該比分段樹好（如果數據足夠大，速度會更快）。

來源

2016-05-19 14:13:15 Sorin

你可以進一步瞭解如何進行分類嗎？你會根據開始時間還是結束時間進行排序？我知道分段樹搜索是O（LogN），但構建樹可能很慢O（Nlogn） – Pinhead

假設您有[10-12]和[11-13]個會議。我用[（10，start），（12，end），（11，start），（13，end）]創建一個單獨的向量，並按小時排序以得到[（10，start），（11，start ），（12，結束），（13，結束）]。現在，如果你經歷了這個過程，當你看到有'開始'的東西時，你可以增加使用的房間數量，當你有'結束'的時候減少它。你只需要找出各種查詢間隔的最大值（一個堆棧會有所幫助）。總的來說，由於排序，你仍然是O（NlogN）。 – Sorin

我們可以使用區間樹來解決這個問題嗎？ –

會議調度程序算法。段樹的情況？

回答

相關問題