524. Maximum CPU Load Problem in a jobs list

Given a list of n Jobs with start time, end time and CPU load when it is active at any moment. If all the jobs are running at the same machine then find the maximum CPU load at any time, Also print the time at which the load was maximum.

Input: Given a list of processes with their start time and end time and the CPU load. For instance process = [0, 2, 5] has to be read as the process starts at time 0 and ends at time 2 ( end time is inclusive, means the process is still running until time 2) and it will put a load to the CPU of 5 units.

Example:

Given Jobs: [[2, 4, 5], [0, 6, 7], [5, 10, 6]]
Maximum CPU Load is: 13 at time: 5

Given Jobs: [[2, 4, 5], [0, 6, 7], [5, 10, 6], [0, 3, 10]]
Maximum CPU Load is: 22 at time: 2

Approach:

Naive Solution: 

Find the time at which the first task has started, call it first_time. Also, find the time at which the last task ended, call it last_time. The duration for running all the tasks would be last_time-first_time+1. Now create a count array of size duration. For each time in duration, check if for a task which starts, add or subtract the count by its load and store it in the count array (there could be multiple tasks start or end at the same time, for each task add or subtract the load in count array). Later, iterate through the count array and find the maximum. 

Time Complexity: O(Duration*N)

Better Solution: 

This solution is similar to Count Maximum overlaps in a given list of time intervals. 

• Initialize max_load = 0. 
• Now We need to keep track of the current_load on the CPU, will update the number every time a task starts (increase the current_load by task load) in or a task ends (decrease the current_load by task load). 
• Another important factor is to make sure that we handle each start or end of the task in ascending order of time then we will get the exact load at the CPU at the given time. So sort the start times and end times in ascending order. Since we have one list of tasks, create two more lists, one sorted with start time and another sorted with end time.
• After each start of the task check if max_load<current_load do max_load=current_load, time = start time of current task. (check after the start of the task because CPU load will increase only after starting a task).

Time Complexity: O(NlogN), N - Number of tasks

Output: 

Given Jobs: [[2, 4, 5], [0, 6, 7], [5, 10, 6], [0, 3, 10]]
Maximum CPU Load is: 22 at time: 2