líneas de base - tabla:Calcular "hora cargada"
fecha/hora de la llamada, duración de la llamada
Cómo calcular "Ocupado hora"?
http://en.wikipedia.org/wiki/Busy_hour - En un sistema de comunicaciones, el período de deslizamiento de 60 minutos durante el cual se produce la carga de tráfico total máxima en un período de 24 horas determinado.
Durante un período prolongado (tantos días como se le puede molestar calcular), calcule el número de llamadas activas en cada minuto del día: hay 1440 de ellas. Luego, para cada minuto del día, calcule la suma móvil de 60 minutos de las llamadas activas, el minuto para el que se maximiza esta suma es el inicio de la hora ocupada (siempre que haya calculado los promedios móviles adelantados). No te olvides de envolver a medianoche.
Esto parece tan simple que sospecho que he entendido mal tu pregunta.
Sume la primera hora y anote la suma. luego agregue todo el tráfico del próximo minuto y elimine el tráfico del primer minuto. Si esta suma es mayor que la primera, anótelo y continúe.
algo como el código crudo aquí
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;
}
Esto se puede hacer en un tiempo lineal, mediante el uso de dos punteros (izquierda y derecha) que atraviesan la lista ordenada de eventos. En realidad, el recorrido se realiza en una lista ordenada de eventos de llamadas, que contiene eventos de inicio de llamada y eventos de fin de llamada.
El puntero izquierdo comienza desde el evento de inicio más a la izquierda. El puntero a la derecha se mueve al evento más reciente a más tardar (hora ptr izquierda + 1 hora). También mantenemos una variable suma que calcula el total de todas las duraciones de llamada en el intervalo.
En cada iteración movemos el puntero izquierdo para el próximo evento (la actualización de la suma en consecuencia), y luego avanzar con el puntero a la derecha (la actualización de la suma, otra vez) hasta su posición final (poco menos de 1 hora más tarde) .
El valor máximo de suma se obtiene en la ventana de hora ocupada.
No proporcioné detalles sobre cómo actualizar la variable de suma al mover los punteros, pero creo que no debería ser complicado hacerlo en tiempo constante.
La ventaja de este algoritmo es que no tiene el problema de granularidad, y que es lineal en el número de eventos.
--EDIT--
En realidad este es un O (N * log N) algoritmo, ya que la mesa de entrada no proporciona la clasificación de los acontecimientos que se supone. Necesitamos generar las listas ordenadas de eventos primero
Tenemos un tipo de mapa de calor 1D.
Ponga las llamadas en el mapa que muestra la hora, luego encuentre la hora más "caliente".
Buena idea, pero esto todavía requiere definir una granularidad de tiempo y consumir el espacio de la matriz en consecuencia. Mi solución (aunque es un poco complicada y no vale la pena para pequeñas entradas) evita esto y ofrece una solución casi lineal en la cantidad de eventos. –
¿No supone eso granularidad minuto? Pude imaginar algunos casos extremos difíciles en los que un volumen de llamadas que variaba segundo a segundo podía perderse. – PaulJWilliams
@Visage: así podría, así que asuma la granularidad de segundo, o la granularidad de milisegundos si eso es lo apropiado para su caso. De cualquier manera, solo tomará un par de minutos calcular. –
Dado que pasar de precisión minuciosa a precisión de milisegundos implicaría un aumento en la magnitud de 10^4 No creo que pueda cancelar la diferencia tan fácilmente. – PaulJWilliams