Algorithm for finding total idle time given array of start/end times

Question

Say you're given a start and end time.

Also you're given an array of jobs, described by their start and end times. These jobs may overlap (ie, there can be multiple jobs running at once). I need to find a way to determine how much time was spent idle and not running any job.

Of course, if only one job can be running at any time, I could just subtract out the running times of each job, but the overlap part has me stumped.

Answer 1

Sort the times, and then run through them in order.
If a time is a start time, add 1 to the number of tasks running.
If it is a stop time, subtract 1.
Keep track of how much time there is when the number of tasks is 0.

Answer 2

Put all the start and end times into a single array, tagging them as either start or end times. Sort the array by time. Now iterate through the sorted list, keeping a count of how many jobs are running by:

• incrementing the counter when reading a start time
• decrementing the counter when reading an end time

Whenever you increment from zero to one, add (current_time - previous_time) to the total idle time. Remember to also special case the start and end if necessary.

Answer 3

Here's a slightly different approach. The first part is for illustrative purpose.

Create an array of ints representing the full timeline of all jobs. This can be in hours, minutes, or whatever you need. I'll assume hours. Find the earliest start time and latest end time to set the size of the array. Initialize all elements to zero.

Loop through each job, incrementing the counter in the timeline for each hour the job is running. So if a job runs from 3pm to 5pm, that's two hours, so you'd increment the 3-hour and the 4-hour slot to indicate that a job was running during those hours.

Loop through the timeline, keeping count of how many zeroes you encounter. Those are the time slots where no job was running.

Now, if you understand that, it's pretty easy to get rid of the array. Instead of creating a (potintially large) array, just keep track of the begin and end time of the entire time line. For each hour in that range loop through all your jobs and see how many are running during that time. Any that are zero are idle times.

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

You have chunks of busy time, when one or more jobs are running. The idle time is the sum of the time spans between the busy chunks. Pseudocode:

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
  }
}

Note: For simplicity, I left out the code to handle the first element.