Problem Statement :
Given an input arrays of Tasks
Input: tasks = [A, A, A, B, B, C, C, D]
and a window of size k = 3 (say)
You have schedule tasks in each CPU cycle.(1 task per CPU cycle or CPU cycle can go idle we well). Idle cycle is represented by "X".
You have to make sure no task gets repeated before k intervals, you ma have to have 'idle' CPU cycle as well in order to achieve this. Find the minimum number of CPU cycles.
for above input
output : A B C D A B C X A X X X A
above output is one possible answer for the given input, if you observe "A" repeats atleast after k=3, for that matter any task repeats at-least after 3 CPU cycles.
Leetcode :
621. Task Scheduler
https://leetcode.com/problems/task-scheduler/
Solution :
This is a very interesting problem, and has been asked in top notch companies.
There are multiple solutions we will be the best approach to solve this. (you can solve this by sorting and using Priority queue as well).
Lets fit the above input into the grid to understand better.
The formula at the end of the above image is crucial, spend time understanding that, thats the crux of the problem.
There is a another interesting case at step 4 in the code below, it occurs when number of idle product of maxCount and k is less compared to total distinct tasks. (i recommend to pay attention to this line carefully). One example of such scenario is ['A' , 'A' , 'B' , 'C' , 'D' , 'E', 'F' ] and k = 2 , by the above formula, your result would be (2 - 1 ) * (2 + 1) + 1 = 4 but the correct answer is 7.
Below is the implementation of the above problem.
Please post comments and suggestions.
Happy Coding !! :)
Given an input arrays of Tasks
Input: tasks = [A, A, A, B, B, C, C, D]
and a window of size k = 3 (say)
You have schedule tasks in each CPU cycle.(1 task per CPU cycle or CPU cycle can go idle we well). Idle cycle is represented by "X".
You have to make sure no task gets repeated before k intervals, you ma have to have 'idle' CPU cycle as well in order to achieve this. Find the minimum number of CPU cycles.
for above input
output : A B C D A B C X A X X X A
above output is one possible answer for the given input, if you observe "A" repeats atleast after k=3, for that matter any task repeats at-least after 3 CPU cycles.
Leetcode :
621. Task Scheduler
https://leetcode.com/problems/task-scheduler/
Solution :
This is a very interesting problem, and has been asked in top notch companies.
There are multiple solutions we will be the best approach to solve this. (you can solve this by sorting and using Priority queue as well).
Lets fit the above input into the grid to understand better.
The formula at the end of the above image is crucial, spend time understanding that, thats the crux of the problem.
There is a another interesting case at step 4 in the code below, it occurs when number of idle product of maxCount and k is less compared to total distinct tasks. (i recommend to pay attention to this line carefully). One example of such scenario is ['A' , 'A' , 'B' , 'C' , 'D' , 'E', 'F' ] and k = 2 , by the above formula, your result would be (2 - 1 ) * (2 + 1) + 1 = 4 but the correct answer is 7.
Below is the implementation of the above problem.
Please post comments and suggestions.
Happy Coding !! :)