CODEWITHSUNDEEP
algorithm
accelerate
accelerate

Reputation: 1353

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

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.

Upvotes: 6

Views: 2827

Answers (6)

Xurahbeel
Xurahbeel

Reputation: 13

We have 2 arrays of start times and end times of jobs. Jobs can overlap as in the following two example arrays.

startTime = [2.1, 5.0, 8.3, 14.1 ,16.5, 24.2 ,28.1, 40.6 ,42.3 , 45.4 ]
endTime =  [4.0 ,10.0 ,9.3 ,18.1 ,26.5 ,25.3, 36.6 ,60.6, 44.3 ,55.4]

We have to calculate the idle time of the system. In this case the calculation is: Total idle time = 2.1 + (5.0-4.0) + (14.1-10.0) + (28.1-26.5) + (40.6-36.6) = 12.8 units

So, the solution is:

startTime = [2.1 , 5.0  , 8.3 , 14.1 , 16.5 , 24.2 , 28.1 , 40.6 , 42.3 ]
endTime =   [4.0 , 10.0 , 9.3 , 18.1 , 26.5 , 25.3 , 36.6 , 60.6 , 44.3 ]

if len(startTime)>0:
    idleTime = startTime[0];
    eT =  endTime[0];
    i = 1 
    while i < len(startTime):
        if startTime[i]>eT:
            idleTime += (startTime[i] -eT)
            eT = endTime[i]
        else:
            if endTime[i]>eT:
                eT = endTime[i]
        i+=1
    print("Idle Time is : " , idleTime )    
else:
    print ("Idle Time is : " , 0 )

Upvotes: 0

Bill the Lizard
Bill the Lizard

Reputation: 405755

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.

Upvotes: 3

mbeckish
mbeckish

Reputation: 10579

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.

Upvotes: 0

aJ.
aJ.

Reputation: 35450

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

Upvotes: 1

moinudin
moinudin

Reputation: 138347

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.

Upvotes: 6

Mike Dunlavey
Mike Dunlavey

Reputation: 40669

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.

Upvotes: 12

Related Questions