algorithm - 用于检查与 N 个任务重叠的时间的更好算法

Question

首先，这是一个针对建议的讨论型问题。假设我有开始和结束时间的任务，当我创建一个新任务时，我想有效地检查与所有现有任务重叠的时间。我目前正在使用什么 -

    checkTaskTimeOverlapping (List<Task> existingTasks, Task newTask){
       List<String> overlappingTimePeriods = new ArrayList<>();

       for(Task existingTask : existingTasks) {
           if( existingTask.beginTime < newTask.endTime && existingTask.endTime > newTask.beginTime) {
                  overlappingTimePeriods.add(existingTask.beginTime+ "-" + existingTask.endTime);     
             }  

       }
    } 

现在如您所见，该算法使用 O(N) 复杂度来检查与 N 个现有任务重叠的时间。现在应该有很多任务，所以..我的问题是，有没有什么方法可以更好地优化这个算法来检查与现有任务重叠的时间，比如说小于 O(N)？或者我应该只保留现有的 O(N) 算法

Answer 1

您可以保持现有任务按开始时间排序，并使用 Collections.binarySearch 获取插入新任务的索引，并与上一个和下一个任务进行比较。那当然是 O(log(N))