Last Updated: 4 Sep, 2021
CPU Task Scheduler
Moderate
Asked in companies
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.
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
Approaches
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”.
Similar problems