Katkat
Back

Rearrange Tasks With Cooldown

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manage dependencies and scheduling constraints using a greedy strategy with a priority queue.

Problem Statement

You are given a list of tasks that need to be executed on a CPU. Each task is represented by a character (e.g., 'A', 'B', 'C'). Due to hardware limitations, there is a mandatory cooldown period k between two identical tasks. This means that if you execute task 'A' at time t, the next time you can execute 'A' is at time t + k + 1 or later.

You must execute all tasks in the given order. If you cannot execute any pending task due to cooldown constraints, you must idle (represented by 'idle') for one unit of time. Your goal is to return the total time units required to complete all tasks.

Function Signature

def calculate_total_time(tasks: List[str], k: int) -> int:

Examples

Example 1:

  • Input: tasks = ['A', 'A', 'A', 'B', 'B', 'B'], k = 2
  • Output: 8
  • Explanation: A -> B -> idle -> A -> B -> idle -> A -> B. Total time is 8.

Example 2:

  • Input: tasks = ['A', 'C', 'A', 'B'], k = 1
  • Output: 5
  • Explanation: A -> C -> A -> B (since 'A' has a cooldown of 1, it cannot repeat immediately, but it is separated by 'C'). Total time is 4 (no, wait: A -> C -> A -> B takes 4 units. If 'A' repeats at index 2, that's fine since it was at index 0, difference is 2, which is > 1).

Constraints

  • tasks length: 1 to 10^4
  • k: 0 to 100
  • tasks contains only uppercase English letters.

Hints

Hint 1

Consider keeping track of the last time each task was executed in a hash map.

Hint 2

At each time step, identify which tasks are available (not currently on cooldown) and pick the one that appears most frequently among the remaining tasks to minimize idle time.

Hint 3

If no tasks are available to be picked at a certain time, you must increment the timer and append an 'idle' count.

Follow-up questions

  • How would your approach change if tasks had different execution durations instead of all taking 1 unit of time?
  • Can you provide a mathematical formula to determine the minimum time required without simulating the schedule?
  • What is the time and space complexity of your solution, and can it be optimized if the number of unique task types is small?