Algoritmo para encontrar el tiempo de inactividad total dado el conjunto de horas de inicio/finalización

Question

Digamos que tiene una hora de inicio y finalización.

También se le ofrece una variedad de trabajos, descritos por sus horas de inicio y finalización. Estos trabajos pueden superponerse (es decir, puede haber múltiples trabajos ejecutándose a la vez). Necesito encontrar una forma de determinar cuánto tiempo pasé inactivo y no ejecutar ningún trabajo.

Por supuesto, si solo se puede ejecutar un trabajo en cualquier momento, podría restar los tiempos de ejecución de cada trabajo, pero la parte de superposición me tiene perplejo.

Answer 1

Poner todos los tiempos de inicio y fin en una sola matriz, etiquetado como ya sea inicio o finalización de los tiempos. Ordenar la matriz por tiempo. Ahora iterar a través de la lista ordenada, manteniendo un recuento de cuántos puestos de trabajo se están ejecutando por:

• incrementar el contador cuando se lee una hora de inicio
• decrementar el contador cuando se lee una hora de finalización

Siempre aumenta de cero a uno, agrega (current_time - previous_time) al tiempo total de inactividad. Recuerde también un caso especial, el inicio y el final si es necesario.

Answer 2

Ordene los tiempos, y luego ejecútelos en orden.
Si una hora es una hora de inicio, agregue 1 a la cantidad de tareas en ejecución.
Si se trata de un tiempo de parada, restar 1.
un seguimiento de cómo mucho tiempo allí es cuando el número de tareas es 0.

Answer 3

Aquí hay un enfoque ligeramente diferente. La primera parte es para fines ilustrativos.

Crea una matriz de entradas que representa la línea de tiempo completa de todos los trabajos. Esto puede ser en horas, minutos o lo que sea que necesite. Asumiré horas. Encuentre la hora de inicio más temprana y la última hora de finalización para establecer el tamaño de la matriz. Inicializa todos los elementos a cero.

Recorra en bucle cada trabajo, incrementando el contador en la línea de tiempo por cada hora que se está ejecutando el trabajo. Entonces, si un trabajo se ejecuta desde las 3 p.m. hasta las 5 p.m., son dos horas, por lo que aumentaría el intervalo de 3 horas y 4 horas para indicar que se estaba ejecutando un trabajo durante esas horas.

Pasa a través de la línea de tiempo, teniendo en cuenta cuántos ceros encuentras. Esos son los intervalos de tiempo en los que no se estaba ejecutando ningún trabajo.

Ahora, si usted entiende eso, es bastante fácil deshacerse de la matriz. En lugar de crear una matriz (potintially large), solo haga un seguimiento de la hora de inicio y finalización de toda la línea de tiempo. Por cada hora en ese rango recorra todos sus trabajos y vea cuántos se están ejecutando durante ese tiempo. Cualquiera que sea cero son tiempos inactivos.

Answer 4

Sort the jobs based on their end times. 

Jobs<startTime,EndTime>[] = contains the Sorted list. 

Take first Job in the list 
Jobs[0] 

intialize: 
    EndTime = Job[0].EndTime 
    StartTime = Job[0].StartTime 
    idleTime =0; 

For i = 1 till Jobs.size 
{ 
    if (Jobs[i].EndTime >= StartTime) 
    { 
     //Do nothing, its overlapping 
    } 
    else 
    { //Previoys Job time doesnot overlap, so get the idle time. 
     idleTime += (StartTime -Jobs[i].EndTime); 
    } 

    StartTime = Jobs[i].StartTime; 
    EndTime = Jobs[i].EndTime; 
} 

Answer 5

Tiene períodos de ocupado, cuando uno o más trabajos se están ejecutando. El tiempo de inactividad es la suma de los intervalos de tiempo entre los fragmentos ocupados. Pseudocódigo:

idle_time = 0 
sort jobs by start time 
foreach job in jobs 
{ 
    if (job.start > current_chunk.end) 
    { 
    idle_time += job.start - current_chunk.end 
    } 
    if (job.end > current_chunk.end) 
    { 
    current_chunk.end = job.end 
    } 
} 

Nota: Para simplificar, me dejó fuera del código para manejar el primer elemento.