CPU Task Scheduler

Moderate
0/80
profile
Contributed by
6 upvotes
Asked in companies
SalesforceGoogle inc

Problem statement

There is a multi-core CPU. A single-core in this CPU can execute only a single task at a given time, so if two tasks need to be executed simultaneously, we will need at least two different cores to process them.

You have been given a list of ‘N’ tasks that need to be executed, this list contains starting and ending times of each task.

Find out the minimum number of cores required in this CPU so that all the tasks can be executed at their scheduled time.

Note: 
If a core is busy executing task-1 then it won’t be able to execute task-2 if the starting time of task-2 is less than the end time of task-1.
Example : 
If N = 4 and the timestamps of the tasks are: { {0,10}, {5,20}, {10,25}, {30,40} }

Then the minimum number of cores required is equal to 2. 
Task-1 will arrive at 0 and core-1 will execute it till 10.
Task-2 will arrive at 5 and as core-1 is busy executing task-1, so core-2 will be assigned and it will execute this task till 20
Task-3 will arrive at 10, core-1 has just finished executing task-1 and is now free, so core-1 will execute this task till 25.
Task-4 will arrive at 30, both core-1 and core-2 are free and any one of them will execute this task.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’ denoting the number of tasks to be executed.

The following N line each contains two integers ‘Start[i]’ and ‘End[i]’ denoting the time-stamp of the ith task.
Output Format : 
For each test case, print a single integer denoting the minimum number of cores required.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 10      
1 <= N <= 1000
0 <= Start[i] < End[i] <= 1’000’000

Time limit: 1 sec
Sample Input 1 :
2
4
0 10
5 20
10 25
30 40
3
1 5
2 4
3 4
Sample Output 1 :
2
3
Explanation For Sample Input 1 :
For test case 1 : 
We will return 2, because:
Task-1 will arrive at 0 and core-1 will execute it till 10.
Task-2 will arrive at 5 and as core-1 is busy, so core-2 will be assigned and it will execute this task till 20
Task-3 will arrive at 10, core-1 has just finished executing task-1 and is now free, so core-1 will execute this task by 25.
Task-4 will arrive at 30, both core-1 and core-2 are free and any one of them will execute this task.


For test case 2 : 
We will return 3, because:
Task-1 will arrive at 1 and core-1 will execute it till 5.
Task-2 will arrive at 2 and as core-1 is busy, so core-2 will execute this task till 4.
Task-3 will arrive at 3, as both core-1 and core-2 are busy executing other tasks, so core-3 will be assigned to execute task-3.
Sample Input 2 :
2
2
5 10
2 8
1
10 11
Sample Output 2 :
2
1
Hint

Firstly sort all the tasks in increasing order of their start time.

Storing all the ending time-stamps of previous tasks is enough to know whether we need a new core for the current task or not.

Approaches (1)
Using Min-Heap

Sort all the tasks in increasing order of their start time. Now maintain a min-heap to store the ending time of all the tasks currently being executed.


Use a variable to store the current size of the min-heap, and the maximum value of this variable while processing each task one by one will be returned as our final answer.


For each task remove the tasks with ending time less than or equal to the start time of the current process as these tasks have already finished executing. Now insert the end time of the current time into the min-heap and proceed to the next task.


The steps are as follows :

  • Sort all the tasks in increasing order of their start time.
  • Create a min-heap “pq” to store the ending time of tasks currently being executed.
  • Initialize an integer “ans” equal to 0 to store the minimum cores required, also initialize an integer “size” equal to 0 to store the current size of the min-heap.
  • Now iterate over each task and start processing it, run a while loop and remove all the tasks whose end time is less than or equal to the current task’s start time, also decrement the value of “size” for each task popped out. Now insert the current task’s end-time in “pq” and increment the value of “size”. Also update the value of “ans” if needed.
  • Finally, return “ans”.
Time Complexity

O( N * log(N) ), where N denotes the number of tasks


We iterate through each task and push its ending time into a min-heap, the insertion time of a min-heap is ~ log ( heap.size ), and the heap size can grow to ~N in a case when all the tasks are clashing with each other.

Hence the time complexity is O( N ).

Space Complexity

O( N ), where N denotes the number of tasks

 

When all the given tasks are clashing with each other, we will end up putting all of them into a min-heap.

Hence the space complexity is O( N ).

Code Solution
(100% EXP penalty)
CPU Task Scheduler
Full screen
Console