用於檢查與N個任務重疊的時間的更好算法

首先，這是一個討論類型的問題，以提供建議。假設我有開始和結束時間的任務，並且當我創建一個新任務時，我想檢查時間與所有現有任務有效地重疊。我目前使用的是什麼 -用於檢查與N個任務重疊的時間的更好算法

現在你可以看到，這個算法使用O（N）的複雜性檢查的時間與N個現有任務重疊。現在應該有很多任務，所以......我的問題是，有什麼方法可以更好地優化這種算法，以檢查與現有任務重疊的時間是否小於O（N）？或者我應該只保留現有的算法O（N）

來源

2017-03-27 adn.911

什麼可以是開始和結束時間的範圍？ – vish4071

大約24小時* 60分鐘從AM/PM格式的1 - 12開始 –

您可以保持現有任務按beginTime排序，並使用Collections.binarySearch獲取插入新任務的索引，並與上一個任務和下一個任務進行比較。那當然會是O（log（N））

來源

2017-03-27 07:19:05

1.如果從非數據庫狀態的數據庫中取出O（NLog（N）），首先將其排序？ 2.即使那樣我能得到overlappingTimePeriods列表？ –

@ adn.911如果不將中間結果保存在某處或對輸入執行額外約束（例如命令），則無法提高O（n）以外的性能。 –

@ adn.911 1.是2.假設數據庫只包含非重疊任務，插入點之前的任務可能（或不可能）重疊（如果existingTasks [i-1] .endTime> newTask.beginTime），則全部直到existingTasks [j] .beginTime> newTask.endTime（對於j> = i）的插入點之後的任務將被添加到列表中。只要不滿足條件，您就可以停止搜索。 –

用於檢查與N個任務重疊的時間的更好算法

回答

相關問題