Medium — Heap | Greedy | Hash Table | Counting

The Problem

Given a list of tasks and a cooldown period n, find the minimum time needed to execute all tasks where identical tasks must be separated by at least n intervals.

Approach

Use a max heap to always process the most frequent tasks first, simulating each time slot by processing up to n+1 tasks in each cycle to respect cooldown constraints. Track remaining task counts and add idle time when necessary.

Time: O(m * log k) · Space: O(k)

Code

import heapq
from collections import Counter

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

        cooldown = 0
        while max_heap:
            temp = []
            for _ in range(n + 1):
                if max_heap:
                    temp.append(heapq.heappop(max_heap) + 1)

            for count in temp:
                if count < 0:
                    heapq.heappush(max_heap, count)

            if max_heap:
                cooldown += n + 1
            else:
                cooldown += len(temp)

        return cooldown

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment