Поиск (количество) перекрытий в списке временных диапазонов

Ответ 1

Следующее должно работать:

• Отсортируйте все ваши значения времени и сохраните начальное или конечное состояние для каждого значения времени.
• Установите numberOfCalls в 0 (счетная переменная)

• Запустите ваши значения времени и:

  • increment numberOfCalls, если значение времени отмечено как "Старт"
  • декремент numberOfCalls, если значение времени отмечено как End
  • отслеживать максимальное значение numberOfCalls во время процесса (и значения времени, когда это происходит)

Сложность: O (n log (n)) для сортировки, O (n) для выполнения всех записей

Ответ 2

Как насчет наивного подхода:

• Возьмите минимум времени начала и наибольшее время окончания (это ваш диапазон R)
• Возьмите кратчайшую продолжительность вызова - d (сортировка, O (nlog n))
• Создать массив C, целых (R/d) целых чисел, инициализировать нуль
• Теперь для каждого вызова добавьте 1 к ячейкам, которые определяют длительность вызова O (n * ceil (R/d))
• Проведите цикл по массиву C и сохраните max (O (n))

Я предполагаю, что вы могли бы моделировать это как график тоже и играть вокруг, но бьет меня в данный момент.

Ответ 3

По-моему, жадный алгоритм сделает нужным. Проблема аналогична выяснению количества платформ, необходимых для расписания заданных поездов. Таким образом, количество перекрытий будет равняться количеству необходимых платформ.
Время сортировки сортируется. Начните размещать каждый вызов в массиве (платформе). Поэтому для вызова i and (i + 1), если callEnd[i] > callStart[i+1], то они не могут попасть в один и тот же массив (или платформу), чтобы поместить столько вызовов в первый массив, насколько это возможно. Затем повторите процесс с остальными до тех пор, пока все вызовы не будут исчерпаны. В итоге количество массивов - это максимальное количество перекрытий. И сложность будет O(n).

Ответ 4

На следующей странице приведены примеры решения этой проблемы на многих языках: http://rosettacode.org/wiki/Max_Licenses_In_Use

Ответ 5

Вы сокращаете список на CallStart. Тогда для каждого элемента (i) вы видите для всех j < i, если

CallEnd[j] > CallStart[i] // put it in a map with CallStart[i]  as the key and some count

Отдых должен быть достаточно простым.

Ответ 6

Удивительно, как для некоторых проблем решения иногда просто выходят из одного ума... и я думаю, что я, вероятно, самое простое решение;)

Вы можете представлять время в секундах, начиная с начала вашего диапазона (0) до конца (600). Вызов пару раз.

Алгоритм Python:

def maxSimultaneousCalls(calls):
  """Returns the maximum number of simultaneous calls
  calls   : list of calls
    (represented as pairs [begin,end] with begin and end in seconds)
  """
  # Shift the calls so that 0 correspond to the beginning of the first call
  min = min([call[0] for call in calls])

  tmpCalls = [(call[0] - min, call[1] - min) for call in calls]
  max = max([call[1] for call in tmpCalls])

  # Find how many calls were active at each second during the interval [0,max]
  seconds = [0 for i in range(0,max+1)]
  for call in tmpCalls:
    for i in range(call[0],call[1]):
      seconds[i] += 1

  return max(seconds)

Обратите внимание, что я не знаю, какие вызовы были активны в данный момент;)

Но с точки зрения сложности это чрезвычайно тривиально, чтобы оценить: он линейный в терминах общей продолжительности вызовов.

Ответ 7

Я думаю, что важным элементом хорошего решения этой проблемы является признание того, что каждое конечное время >= время начала вызова и время начала заказа. Поэтому вместо того, чтобы думать о прочтении всего списка и сортировке, нам нужно только прочитать по порядку времени начала и слить из мини-кучи времени окончания. Это также относится к комментарию Санджива о том, как концы должны быть обработаны до начала, когда у них есть то же самое значение времени путем опроса с минимальной кучи времени окончания и выбора его, когда это значение равно <= следующее время начала.

max_calls = 0
// A min-heap will typically do the least amount of sorting needed here.
// It size tells us the # of currently active calls.
// Note that multiple keys with the same value must be supported.
end_times = new MinHeap()
for call in calls:
  end_times.add(call.end)
  while (end_times.min_key() <= call.start) {
    end_times.remove_min()
  }
  // Check size after calls have ended so that a start at the same time
  // doesn't count as an additional call.  
  // Also handles zero duration calls as not counting.
  if (end_times.size() > max_calls) max_calls = end_times.size()
}

Ответ 8

Это похоже на операцию reduce. Аналогия заключается в том, что при каждом запуске вызова текущее количество активных вызовов увеличивается на 1. Каждый раз, когда вызов завершается, текущее количество вызовов падает до нуля.

Когда у вас есть этот поток активных вызовов, вам нужно всего лишь применить к ним максимальную операцию. Вот рабочий пример python2:

from itertools import chain
inp = ((123, 125),
       (123, 130),
       (123, 134),
       (130, 131),
       (130, 131),
       (130, 132),)

# technical: tag each point as start or end of a call
data = chain(*(((a, 'start'), (b, 'end')) for a, b in inp))

def r(state, d):
    last = state[-1]
    # if a call is started we add one to the number of calls,
    # if it ends we reduce one
    current = (1 if d[1] == 'start' else -1)
    state.append(last + current)
    return state

max_intersect = max(reduce(r, sorted(data), [0]))

print max_intersect

Ответ 9

Вот рабочий алгоритм в Python

def maximumOverlap(calls):
    times = []
    for call in calls:
        startTime, endTime = call
        times.append((startTime, 'start'))
        times.append((endTime, 'end'))
    times = sorted(times)

    count = 0
    maxCount = 0
    for time in times:
        if time[1] == 'start':
            count += 1    # increment on arrival/start
        else:
            count -= 1    # decrement on departure/end
        maxCount = max(count, maxCount)  # maintain maximum
    return maxCount

calls = [
('2:22:22 PM', '2:22:33 PM'),
('2:22:35 PM', '2:22:42 PM'),
('2:22:36 PM', '2:22:43 PM'),
('2:22:46 PM', '2:22:54 PM'),
('2:22:49 PM', '2:27:21 PM'),
('2:22:57 PM', '2:23:03 PM'),
('2:23:29 PM', '2:23:40 PM'),
('2:24:08 PM', '2:24:14 PM'),
('2:27:37 PM', '2:39:14 PM'),
('2:27:47 PM', '2:27:55 PM'),
('2:29:04 PM', '2:29:26 PM'),
('2:29:31 PM', '2:29:43 PM'),
('2:29:45 PM', '2:30:10 PM'),
]
print(maximumOverlap(calls))