Compute minimum time with task cooldowns
Company: Chime
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a multiset of task types represented by uppercase letters (e.g., A, A, A, B, B, C). Each task takes exactly 1 time unit to execute. Running the same task type requires at least c cooldown time units between two executions of that type. You may reorder tasks and insert idle slots as needed. Compute the minimum total time units to finish all tasks. Describe an algorithm, justify its correctness, analyze time and space complexity, and explain how to construct one optimal schedule.
Quick Answer: This question evaluates understanding of constrained task scheduling, frequency-based reasoning, and algorithmic complexity within the Coding & Algorithms domain (task scheduling and combinatorial optimization), emphasizing both conceptual understanding and practical application.
You are given a multiset of task types represented by uppercase letters. Each task takes exactly 1 time unit to execute. If the same task type is executed more than once, there must be at least c full time units between two executions of that type. You may reorder the tasks in any order and insert idle time slots if needed. Return the minimum total number of time units needed to complete all tasks.
For example, with tasks ['A','A','A','B','B','B'] and c = 2, one optimal schedule is A, B, idle, A, B, idle, A, B, which takes 8 time units.
Constraints
- 0 <= len(tasks) <= 100000
- Each task is an uppercase English letter from 'A' to 'Z'
- 0 <= c <= 100000
- Each task takes exactly 1 time unit
Examples
Input: (['A','A','A','B','B','B'], 2)
Expected Output: 8
Explanation: One optimal schedule is A, B, idle, A, B, idle, A, B. The total time is 8.
Input: (['A','A','A','B','B','C'], 2)
Expected Output: 7
Explanation: One optimal schedule is A, B, C, A, B, idle, A. The final A executions are separated by at least 2 time units.
Hints
- The task type with the highest frequency determines the minimum number of separated groups you may need.
- Think of arranging the most frequent tasks first, then filling the gaps with other tasks before deciding whether idle slots are necessary.