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

Question

Учитывая список временных диапазонов, мне нужно найти максимальное количество перекрытий.

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

CallStart   CallEnd
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

Если кто-то знает алогрит или может указать мне правильное направление, я был бы признателен.

ТИА

Стив F

Answer 1

Должны работать следующие:

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

3. Просмотрите значения времени и:

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

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

Answer 2

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

Answer 3

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

Answer 4

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

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

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

Answer 5

Вот рабочий алгоритм на 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))

Answer 6

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

Когда у вас есть этот поток активных вызовов, все, что вам нужно, это применить к ним операцию max. Вот рабочий пример 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

Answer 7

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

max_calls = 0
// A min-heap will typically do the least amount of sorting needed here.
// It's 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()
}

Answer 8

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

Вы можете представить время в секундах от начала диапазона (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)

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

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

Answer 9

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

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

Отдых должен быть достаточно легким.