Рассчитать "Занятый час"

Question

Базовые показатели - таблица:

дата / время звонка, продолжительность звонка

Как рассчитать "Занятый час"?

http://en.wikipedia.org/wiki/Busy_hour - В системе связи скользящий 60-минутный период, в течение которого происходит максимальная общая нагрузка трафика за данный 24-часовой период.

Answer 1

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

Это кажется настолько простым, что я подозреваю, что неправильно понял ваш вопрос.

Answer 2

Это можно сделать за линейное время, используя два указателя (влево и вправо), пересекающих отсортированный список событий.Фактически, обход выполняется в отсортированном списке событий вызова, который содержит как события начала вызова, так и события окончания вызова.

Левый указатель начинается с самого левого события запуска.Правый указатель перемещается к последнему событию не позднее (время левого времени + 1 час).Мы также поддерживаем переменную sum , которая вычисляет сумму всех длительностей вызовов в интервале.

На каждой итерации мы перемещаем левый указатель к следующему событию (соответственно обновляя сумму), а затем продвигаемся по правому указателю (снова обновляя сумму) до его конечной позиции (чуть менее 1 часа).позже).

Максимальное значение сумма получено в окне занятого часа.

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

Преимущество этого алгоритма состоит в том, что он не имеет проблемы гранулярности, и что он является линейным по количеству событий.

- РЕДАКТИРОВАТЬ -

На самом деле это алгоритм O (N * Log N), поскольку входная таблица не обеспечивает сортировку событий, которые я предполагал.Сначала нужно сгенерировать отсортированные списки событий

Answer 3

Имейте своего рода 1D тепловую карту.

Сложите вызовы на карту, которая показывает время, затем найдите «самый горячий» час.

Answer 4

суммируйте первый час и запишите сумму. затем добавьте весь трафик следующей минуты и удалите трафик первой минуты. Если эта сумма больше первой, запишите ее и продолжайте.

что-то вроде сырого кода здесь

Minute busyHourStart = 0;
Minute currentStart = 0;
int busyHourSum = 0;
int currentSum = 0;


while( minutesLeft){

   currentSum = sumTrafficForMinutes(currentStart, currentStart + 60);

   if(busyHourSum < currentSum){
      busyHourSum = currentSum
      busyHourStart = currentStart;
   }

    ++currentStart;
}