View on NeetCode
View on LeetCode

Problem

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation:
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

Example 2:

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: On this case any permutation of size 6 would work since n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
And so on.

Example 3:

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation:
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

Constraints:

• 1 <= task.length <= 10^4
• tasks[i] is upper-case English letter.
• The integer n is in the range [0, 100].

Solution

Approach: Max Heap + Queue

The key insight is to always schedule the most frequent task (greedily) while respecting cooldown. Use a max heap for available tasks and a queue for tasks in cooldown.

Implementation

import heapq
from collections import Counter, deque

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        # Count task frequencies
        count = Counter(tasks)
        max_heap = [-cnt for cnt in count.values()]
        heapq.heapify(max_heap)

        time = 0
        queue = deque()  # (count, idle_time)

        while max_heap or queue:
            time += 1

            if max_heap:
                count = -heapq.heappop(max_heap) - 1
                if count > 0:
                    queue.append((count, time + n))

            # Check if any task finished cooldown
            if queue and queue[0][1] == time:
                heapq.heappush(max_heap, -queue.popleft()[0])

        return time

Math Formula Approach:

from collections import Counter

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        # Count frequencies
        count = Counter(tasks)
        max_freq = max(count.values())

        # Count tasks with max frequency
        max_count = sum(1 for c in count.values() if c == max_freq)

        # Calculate minimum intervals
        # (max_freq - 1) complete cycles of (n + 1) slots
        # Plus final max_count tasks
        intervals = (max_freq - 1) * (n + 1) + max_count

        # Answer is max of calculated intervals or total tasks
        return max(intervals, len(tasks))

Complexity Analysis

Heap + Queue:

• Time Complexity: O(n * m), where n is total tasks and m is number of unique tasks. Each task processed once.
• Space Complexity: O(m) for heap and queue.

Math Formula:

• Time Complexity: O(n) for counting frequencies.
• Space Complexity: O(1) or O(26) for counting.

Key Insights

1. Greedy Strategy: Always schedule the most frequent task first to minimize idle time.

2. Cooldown Queue: Tasks in cooldown go into a queue with their available time, then return to the heap.

3. Math Formula: The minimum time is determined by the most frequent task and cooldown period. Visualize as: most_frequent tasks with (n+1) gaps between them.

4. Edge Cases: When many different tasks exist, we may not need any idle time. Formula handles this with max(calculated, total_tasks).

5. Time Flows: Even when no task is scheduled (idle), time still increments.