EngineersofAI LogoCoursesBlogResearch LabAI LettersThe LabCode BankInteractive 3DKodrEarnestJobs
Skip to main content

Python Heap and Priority Queue Practice Problems & Exercises

Practice: Heap and Priority Queue

11 problems4 Easy4 Medium3 Hard⏱ 40–55 min
← Back to lesson

Easy​

#1Predict the Heap OutputEasy
heapqheappushheappoppredict-output

Predict the output of every print call before running the code. Focus on what heap[0] holds after each operation.

Python
import heapq

data = [5, 3, 8, 1, 4, 2, 7]
heapq.heapify(data)
print(f"After heapify: {data[0]}")

print(f"Pop 1: {heapq.heappop(data)}")
print(f"Pop 2: {heapq.heappop(data)}")

heapq.heappush(data, 0)
print(f"After push 0: {data[0]}")

print(f"Pop 3: {heapq.heappop(data)}")
print(f"Remaining min: {data[0]}")
Solution
After heapify: 1
Pop 1: 1
Pop 2: 2
After push 0: 0
Pop 3: 0
Remaining min: 3

Key insights:

  • After heapify: The list is rearranged so the minimum (1) sits at index 0. The internal order is a valid min-heap but NOT fully sorted.
  • Pop 1: Removes and returns 1 (the minimum). Heap now has elements 2, 3, 4, 5, 7, 8.
  • Pop 2: Removes and returns 2 (the new minimum). Heap now has 3, 4, 5, 7, 8.
  • Push 0: Inserts 0 and sifts it up to the root since it is smaller than everything. data[0] is now 0.
  • Pop 3: Removes and returns 0.
  • Remaining min: The smallest remaining element is 3.

Takeaway: heappop() always returns the current minimum. The internal list layout between index 1 and the end is NOT sorted — only the root is guaranteed to be the minimum.

Expected Output
After heapify: 1
Pop 1: 1
Pop 2: 2
After push 0: 0
Pop 3: 0
Remaining min: 3
Hints

Hint 1: heapify() transforms the list in-place so that heap[0] is always the minimum element.

Hint 2: heappop() removes and returns the smallest element. The next smallest then bubbles to index 0.

Hint 3: heappush() inserts the value and sifts it up to maintain the heap invariant.

#2Find K Smallest ElementsEasy
heapqnsmallestbasics

Use heapq.nsmallest to return the k smallest elements from a list. The result should be in ascending order.

Solution
import heapq

def k_smallest(nums, k):
    return heapq.nsmallest(k, nums)

print(k_smallest([7, 2, 9, 1, 5, 3], 3))        # [1, 2, 3]
print(k_smallest([10, 20, 30, 40, 50], 1))       # [10]
print(k_smallest([5, 5, 5, 5], 2))               # [5, 5]
print(k_smallest(list(range(100, 0, -1)), 5))     # [1, 2, 3, 4, 5]

Key insights:

  • heapq.nsmallest(k, data) returns a sorted list of the k smallest elements.
  • Complexity is O(n log k) — much better than O(n log n) sorting when k is small relative to n.
  • For k=1, internally CPython optimizes to just call min() — O(n).
  • The result is always in ascending order regardless of input order.
Starter Code
import heapq

def k_smallest(nums, k):
  # Return the k smallest elements from nums in ascending order.
  # Use heapq.nsmallest().
  # TODO: implement
  pass

# Test cases — do not modify
print(k_smallest([7, 2, 9, 1, 5, 3], 3))
print(k_smallest([10, 20, 30, 40, 50], 1))
print(k_smallest([5, 5, 5, 5], 2))
print(k_smallest(list(range(100, 0, -1)), 5))
Expected Output
[1, 2, 3]
[10]
[5, 5]
[1, 2, 3, 4, 5]
Hints

Hint 1: heapq.nsmallest(k, iterable) returns the k smallest elements as a sorted list.

Hint 2: This is more efficient than sorted(nums)[:k] when k is much smaller than len(nums).

#3Max Heap with NegationEasy
heapqmax-heapnegation-trick

Python's heapq only provides a min-heap. Use the negation trick to simulate a max-heap: store -x so that the smallest negated value corresponds to the largest original value. Pop the three largest elements and return them in descending order.

Solution
import heapq

def three_largest_via_max_heap(nums):
    max_heap = [-x for x in nums]
    heapq.heapify(max_heap)

    result = []
    for _ in range(3):
        result.append(-heapq.heappop(max_heap))
    return result

print(three_largest_via_max_heap([4, 1, 7, 3, 8, 5, 2, 9, 6]))  # [9, 8, 7]
print(three_largest_via_max_heap([10, 10, 10, 5, 5]))             # [10, 10, 10]
print(three_largest_via_max_heap([100, 200, 300]))                 # [300, 200, 100]

Key insights:

  • Negate all values before heapify: [-x for x in nums]. The list [-4, -1, -7, ...] forms a min-heap where -9 is the smallest, meaning 9 is the largest original value.
  • Use heapify() for O(n) construction instead of n individual heappush() calls.
  • Negate back on pop: -heapq.heappop(max_heap) restores the original positive value.
  • This is the standard Python idiom for max-heaps. There is no built-in max-heap in heapq.
Starter Code
import heapq

def three_largest_via_max_heap(nums):
  # Build a max-heap using the negation trick.
  # Pop the 3 largest elements and return them
  # as a list in descending order: [largest, 2nd, 3rd].
  # TODO: implement
  pass

# Test cases — do not modify
print(three_largest_via_max_heap([4, 1, 7, 3, 8, 5, 2, 9, 6]))
print(three_largest_via_max_heap([10, 10, 10, 5, 5]))
print(three_largest_via_max_heap([100, 200, 300]))
Expected Output
[9, 8, 7]
[10, 10, 10]
[300, 200, 100]
Hints

Hint 1: To simulate a max-heap, negate every value before pushing: heapq.heappush(heap, -x).

Hint 2: When you pop, negate the result back: largest = -heapq.heappop(heap).

Hint 3: You can also heapify a list of negated values for O(n) construction.

#4Heapify vs Repeated PushEasy
heapqheapifycomplexitypredict-output

Predict the output and explain why both approaches produce the same logical result but differ in performance.

Python
import heapq

data = [5, 3, 8, 1, 4, 2, 7, 6, 9, 0]

# Approach A: heapify (O(n))
heap_a = data[:]
heapq.heapify(heap_a)
print(f"heapify result min: {heap_a[0]}")

# Approach B: push one by one (O(n log n))
heap_b = []
for x in data:
    heapq.heappush(heap_b, x)
print(f"push-loop result min: {heap_b[0]}")

# Both are valid heaps with the same elements
print(f"Same contents: {sorted(heap_a) == sorted(heap_b)}")
print("heapify is O(n), push-loop is O(n log n)")
Solution
heapify result min: 1
push-loop result min: 1
Same contents: True
heapify is O(n), push-loop is O(n log n)

Key insights:

  • Both approaches yield a valid min-heap with the same set of elements and the same minimum at index 0.
  • The internal array layouts may differ — heap ordering is not unique. Multiple valid arrangements exist for the same set of elements.
  • heapify() is O(n) because it uses a bottom-up sift-down approach. Most nodes are leaves and require zero work.
  • Pushing n elements one at a time is O(n log n) because each heappush may sift up to the root — O(log n) per element.
  • Rule: Always use heapify() when you have the full data upfront. Only use heappush() in a loop when elements arrive one at a time (streaming).
Expected Output
heapify result min: 1
push-loop result min: 1
Same contents: True
heapify is O(n), push-loop is O(n log n)
Hints

Hint 1: Both approaches produce a valid min-heap, but heapify() is O(n) while pushing one by one is O(n log n).

Hint 2: heapify() works bottom-up — most nodes near the leaves do very little work.

Medium​

#5K-th Largest ElementMedium
heapqtop-kmin-heap-of-size-k

Find the k-th largest element in a list using a min-heap of size k. Do not use sorted() or heapq.nlargest(). This is a classic interview problem (LeetCode 215).

Solution
import heapq

def kth_largest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

print(kth_largest([3, 2, 1, 5, 6, 4], 2))           # 5
print(kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))   # 4
print(kth_largest([1], 1))                             # 1
print(kth_largest([7, 7, 7, 7], 3))                    # 7

Why this works:

  • The min-heap always holds the k largest elements seen so far.
  • When we push a new element and the heap exceeds size k, we pop the smallest. This evicts values that are too small to be in the top-k.
  • After scanning all elements, heap[0] is the smallest of the k largest — which is the k-th largest by definition.
  • Time: O(n log k) — each of n elements is pushed/popped at most once, each operation is O(log k).
  • Space: O(k) — the heap never exceeds size k.
Starter Code
import heapq

def kth_largest(nums, k):
  # Return the k-th largest element in nums.
  # Use a min-heap of size k.
  # Do NOT use sorted() or nlargest().
  # TODO: implement
  pass

# Test cases — do not modify
print(kth_largest([3, 2, 1, 5, 6, 4], 2))
print(kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))
print(kth_largest([1], 1))
print(kth_largest([7, 7, 7, 7], 3))
Expected Output
5
4
1
7
Hints

Hint 1: Maintain a min-heap of size k. Push each element. When the heap exceeds size k, pop the smallest.

Hint 2: After processing all elements, heap[0] is the k-th largest — it is the smallest among the top-k.

Hint 3: Time complexity: O(n log k). Space: O(k).

#6Priority Queue with TuplesMedium
heapqpriority-queuetuplesscheduling

Build a simple task scheduler using a heap of (priority, task_name) tuples. Process tasks from highest priority (lowest number) to lowest priority. When two tasks share the same priority, they should come out in alphabetical order by name (tuple comparison handles this).

Solution
import heapq

def process_tasks(tasks):
    heap = list(tasks)
    heapq.heapify(heap)

    order = []
    while heap:
        priority, name = heapq.heappop(heap)
        order.append(name)
    return order

tasks1 = [(3, "email"), (1, "deploy"), (2, "review"), (1, "hotfix")]
print(process_tasks(tasks1))  # ['deploy', 'hotfix', 'review', 'email']

tasks2 = [(5, "docs"), (5, "tests"), (5, "lint"), (1, "build")]
print(process_tasks(tasks2))  # ['build', 'docs', 'lint', 'tests']

Key insights:

  • Python compares tuples lexicographically: first by priority, then by task_name as a tiebreaker.
  • For tasks1: "deploy" (1) and "hotfix" (1) share priority 1. The string "deploy" comes before "hotfix" alphabetically, so "deploy" comes first.
  • For tasks2: "docs", "lint", "tests" all share priority 5 — they come out alphabetically.
  • Pitfall: If the second tuple element is a custom object without __lt__, equal priorities cause a TypeError. Use the counter trick (priority, counter, item) to avoid this.
Starter Code
import heapq

def process_tasks(tasks):
  # tasks is a list of (priority, task_name) tuples.
  # Lower priority number = higher importance.
  # Process all tasks in priority order and return
  # a list of task names in the order they were processed.
  # TODO: implement using a heap
  pass

# Test cases — do not modify
tasks1 = [(3, "email"), (1, "deploy"), (2, "review"), (1, "hotfix")]
print(process_tasks(tasks1))

tasks2 = [(5, "docs"), (5, "tests"), (5, "lint"), (1, "build")]
print(process_tasks(tasks2))
Expected Output
['deploy', 'hotfix', 'review', 'email']
['build', 'docs', 'lint', 'tests']
Hints

Hint 1: Push each (priority, task_name) tuple onto a heap. Python compares tuples element by element.

Hint 2: When priorities are equal, Python compares the second element (the string) — so equal-priority tasks sort alphabetically.

Hint 3: Pop all elements from the heap to get them in priority order.

#7Sort a Nearly-Sorted ArrayMedium
heapqk-sortedsliding-windowstreaming

Given an array where every element is at most k positions from its correct sorted position, sort it efficiently using a heap of size k+1. This is faster than a full sort — O(n log k) instead of O(n log n).

Solution
import heapq

def sort_nearly_sorted(nums, k):
    heap = []
    result = []

    for i, num in enumerate(nums):
        heapq.heappush(heap, num)
        if len(heap) > k:
            result.append(heapq.heappop(heap))

    while heap:
        result.append(heapq.heappop(heap))

    return result

print(sort_nearly_sorted([3, 2, 1, 5, 4, 7, 6, 8], 2))  # [1, 2, 3, 4, 5, 6, 7, 8]
print(sort_nearly_sorted([6, 5, 3, 2, 8, 10, 9], 3))     # [2, 3, 5, 6, 8, 9, 10]
print(sort_nearly_sorted([1, 2, 3, 4, 5], 0))             # [1, 2, 3, 4, 5]

Why this works:

  • Since each element is at most k positions away, the smallest unsorted element must be within the first k+1 elements of the remaining input.
  • We maintain a min-heap of at most k+1 elements. Once the heap has more than k elements, the minimum is guaranteed to be the next element in sorted order.
  • Time: O(n log k) — each of n elements is pushed and popped once, and heap size never exceeds k+1.
  • Space: O(k) — the heap holds at most k+1 elements.
  • When k=0: Each element is already in its correct position. The heap has size 1, and we just pop immediately — effectively a copy.
  • This pattern appears in real systems: merging nearly-sorted log streams, sorting sensor data that arrives slightly out of order.
Starter Code
import heapq

def sort_nearly_sorted(nums, k):
  # Each element in nums is at most k positions away from
  # its correct sorted position.
  # Sort the array efficiently using a min-heap of size k+1.
  # Return the sorted list.
  # TODO: implement
  pass

# Test cases — do not modify
print(sort_nearly_sorted([3, 2, 1, 5, 4, 7, 6, 8], 2))
print(sort_nearly_sorted([6, 5, 3, 2, 8, 10, 9], 3))
print(sort_nearly_sorted([1, 2, 3, 4, 5], 0))
Expected Output
[1, 2, 3, 4, 5, 6, 7, 8]
[2, 3, 5, 6, 8, 9, 10]
[1, 2, 3, 4, 5]
Hints

Hint 1: Since each element is at most k away from its final position, you only need to consider a window of k+1 elements at a time.

Hint 2: Maintain a min-heap of size k+1. Push the first k+1 elements. Then for each remaining element, pop the min (it is the next sorted value) and push the new element.

Hint 3: After all elements are consumed, pop the remaining heap elements to finish the sorted output.

#8Top K Frequent ElementsMedium
heapqtop-kfrequencycounter

Given a list of integers, return the k most frequent elements. Use a heap-based approach — do not simply sort the frequency dictionary. This is LeetCode 347.

Solution
import heapq
from collections import Counter

def top_k_frequent(nums, k):
    counts = Counter(nums)

    heap = []
    for num, freq in counts.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)

    return [num for freq, num in heap]

print(sorted(top_k_frequent([1,1,1,2,2,3], 2)))     # [1, 2]
print(sorted(top_k_frequent([4,4,4,4,5,5,6], 1)))   # [4]
print(sorted(top_k_frequent([1,2,3,4,5], 3)))        # [1, 2, 3]

Key insights:

  • Count frequencies first with Counter: O(n).
  • Use a min-heap of size k to track the top-k frequencies. Push (frequency, element). When the heap exceeds size k, pop the smallest frequency — it cannot be in the top-k.
  • After processing all unique elements (at most n), the heap holds exactly the k most frequent.
  • Time: O(n + m log k) where m is the number of unique elements. Since m is at most n, this is O(n log k).
  • Alternative: heapq.nlargest(k, counts.items(), key=lambda x: x[1]) does the same in one line.
Starter Code
import heapq
from collections import Counter

def top_k_frequent(nums, k):
  # Return the k most frequent elements in nums.
  # If multiple elements have the same frequency,
  # any order among them is acceptable.
  # Use a heap — do NOT just sort the frequency list.
  # TODO: implement
  pass

# Test cases — do not modify
print(sorted(top_k_frequent([1,1,1,2,2,3], 2)))
print(sorted(top_k_frequent([4,4,4,4,5,5,6], 1)))
print(sorted(top_k_frequent([1,2,3,4,5], 3)))
Expected Output
[1, 2]
[4]
[1, 2, 3]
Hints

Hint 1: First count frequencies with collections.Counter. Then use a heap to find the top-k by frequency.

Hint 2: Maintain a min-heap of size k keyed by frequency: push (freq, element). If heap size exceeds k, pop the smallest frequency.

Hint 3: After processing all unique elements, the heap contains the k most frequent. Extract just the element values.

Hard​

#9Merge K Sorted ListsHard
heapqmergesorted-listsclassic-interview

Merge k sorted lists into one sorted list using a min-heap. The heap should hold at most one element from each list at any time. This is LeetCode 23 and a common interview classic.

Solution
import heapq

def merge_k_sorted(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    result = []
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)

        next_idx = elem_idx + 1
        if next_idx < len(lists[list_idx]):
            next_val = lists[list_idx][next_idx]
            heapq.heappush(heap, (next_val, list_idx, next_idx))

    return result

print(merge_k_sorted([[1, 4, 7], [2, 5, 8], [3, 6, 9]]))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

print(merge_k_sorted([[1, 3, 5, 7], [2, 4, 6, 8], [0, 9, 10]]))
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

print(merge_k_sorted([[], [1], [0, 2]]))
# [0, 1, 2]

print(merge_k_sorted([]))
# []

How it works step-by-step (first test case):

  1. Initialize heap with first elements: [(1, 0, 0), (2, 1, 0), (3, 2, 0)]
  2. Pop (1, 0, 0) — value 1 from list 0. Push list 0's next element: (4, 0, 1).
  3. Pop (2, 1, 0) — value 2 from list 1. Push (5, 1, 1).
  4. Pop (3, 2, 0) — value 3 from list 2. Push (6, 2, 1).
  5. Continue until all elements are consumed.

Complexity:

  • Time: O(n log k) — n total elements, each pushed and popped once. Each heap operation is O(log k) since the heap holds at most k entries.
  • Space: O(k) for the heap, plus O(n) for the output.
  • The tuple (value, list_idx, elem_idx) ensures correct comparison: ties in value break by list index, then by element index — all integers, so no TypeError.
Starter Code
import heapq

def merge_k_sorted(lists):
  # Merge k sorted lists into a single sorted list.
  # Use a min-heap to track the current smallest element
  # across all lists.
  # Return the merged sorted list.
  # TODO: implement
  pass

# Test cases — do not modify
print(merge_k_sorted([[1, 4, 7], [2, 5, 8], [3, 6, 9]]))
print(merge_k_sorted([[1, 3, 5, 7], [2, 4, 6, 8], [0, 9, 10]]))
print(merge_k_sorted([[], [1], [0, 2]]))
print(merge_k_sorted([]))
Expected Output
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[0, 1, 2]
[]
Hints

Hint 1: Initialize the heap with the first element from each non-empty list, along with the list index and element index: (value, list_idx, elem_idx).

Hint 2: Pop the smallest, append to result, then push the next element from the same list (if any).

Hint 3: The heap never exceeds size k (the number of lists), giving O(n log k) total time.

#10Running Median from a StreamHard
heapqtwo-heapsrunning-mediandesign

Design a MedianFinder class that supports adding numbers from a stream and finding the current median in O(1) time. Use the two-heap technique: a max-heap for the lower half and a min-heap for the upper half. This is LeetCode 295.

Solution
import heapq

class MedianFinder:
    def __init__(self):
        self.max_heap = []   # lower half, stored negated
        self.min_heap = []   # upper half

    def add_num(self, num):
        # Always push to max_heap first
        heapq.heappush(self.max_heap, -num)

        # Ensure max of lower half <= min of upper half
        if self.max_heap and self.min_heap and (-self.max_heap[0] > self.min_heap[0]):
            val = -heapq.heappop(self.max_heap)
            heapq.heappush(self.min_heap, val)

        # Rebalance sizes
        if len(self.max_heap) > len(self.min_heap) + 1:
            val = -heapq.heappop(self.max_heap)
            heapq.heappush(self.min_heap, val)
        elif len(self.min_heap) > len(self.max_heap):
            val = heapq.heappop(self.min_heap)
            heapq.heappush(self.max_heap, -val)

    def find_median(self):
        if len(self.max_heap) > len(self.min_heap):
            return float(-self.max_heap[0])
        return (-self.max_heap[0] + self.min_heap[0]) / 2.0

mf = MedianFinder()
for val in [5, 2, 8, 1, 9]:
    mf.add_num(val)
    print(mf.find_median())
# 5.0, 3.5, 5.0, 3.5, 5.0

print("---")
mf2 = MedianFinder()
for val in [1, 2, 3, 4]:
    mf2.add_num(val)
    print(mf2.find_median())
# 1.0, 1.5, 2.0, 2.5

How the two-heap approach works:

  • max_heap (negated) holds the smaller half. Its root (negated back) is the maximum of the lower half.
  • min_heap holds the larger half. Its root is the minimum of the upper half.
  • Size invariant: max_heap has the same size or exactly one more element than min_heap.
  • Value invariant: max of lower half is always less than or equal to min of upper half.
  • Median: If odd total count, the median is the root of max_heap. If even, it is the average of both roots.

Complexity:

  • add_num: O(log n) — at most a constant number of heap pushes/pops.
  • find_median: O(1) — just reading the roots.
Starter Code
import heapq

class MedianFinder:
  # Maintain the running median of a stream of numbers.
  # Use two heaps:
  #   - max_heap (negated): stores the smaller half
  #   - min_heap: stores the larger half
  # Invariant: max_heap has the same size or one more element than min_heap.
  #
  # TODO: implement __init__, add_num, and find_median

  def __init__(self):
      pass

  def add_num(self, num):
      pass

  def find_median(self):
      # Return the median as a float.
      pass

# Test cases — do not modify
mf = MedianFinder()
for val in [5, 2, 8, 1, 9]:
  mf.add_num(val)
  print(mf.find_median())

print("---")
mf2 = MedianFinder()
for val in [1, 2, 3, 4]:
  mf2.add_num(val)
  print(mf2.find_median())
Expected Output
5.0
3.5
5.0
3.5
5.0
---
1.0
1.5
2.0
2.5
Hints

Hint 1: The max_heap (negated) holds the lower half. The min_heap holds the upper half. The median is either the max of the lower half or the average of both tops.

Hint 2: After adding a number, rebalance: if the max of the lower half exceeds the min of the upper half, move elements between heaps.

Hint 3: Also rebalance sizes: the max_heap can have at most one more element than min_heap. If min_heap is bigger, move its top to max_heap.

#11Task Scheduler with CooldownHard
heapqmax-heapschedulinggreedysimulation

Given a list of tasks (characters) and a cooldown interval n, compute the minimum time units needed to execute all tasks. The same task must wait at least n units between consecutive executions. Idle time is allowed. Use a max-heap to always schedule the most frequent remaining task. This is LeetCode 621.

Solution
import heapq
from collections import Counter, deque

def least_interval(tasks, n):
    counts = Counter(tasks)
    # Max-heap of remaining counts (negated)
    max_heap = [-cnt for cnt in counts.values()]
    heapq.heapify(max_heap)

    # Cooldown queue: (available_time, negated_remaining_count)
    cooldown = deque()
    time = 0

    while max_heap or cooldown:
        time += 1

        # Move tasks off cooldown if their wait is over
        if cooldown and cooldown[0][0] <= time:
            _, cnt = cooldown.popleft()
            heapq.heappush(max_heap, cnt)

        if max_heap:
            cnt = heapq.heappop(max_heap)
            cnt += 1  # was negated, so +1 means "one fewer remaining"
            if cnt < 0:  # still has remaining executions
                cooldown.append((time + n + 1, cnt))
        # else: idle slot — nothing to schedule this unit

    return time

print(least_interval(["A","A","A","B","B","B"], 2))        # 8
print(least_interval(["A","A","A","B","B","B"], 0))         # 6
print(least_interval(["A","A","A","A","B","B","C","C"], 2)) # 8

How the algorithm works (first test case: A=3, B=3, n=2):

  1. Max-heap: [-3, -3] (A and B each appear 3 times).
  2. Time 1: Pop -3 (A, 3 remaining). Execute A. Remaining: 2. Cooldown until time 4. Heap: [-3].
  3. Time 2: Pop -3 (B, 3 remaining). Execute B. Remaining: 2. Cooldown until time 5. Heap: [].
  4. Time 3: Heap empty, cooldown not ready. Idle.
  5. Time 4: A comes off cooldown. Pop -2 (A). Execute A. Remaining: 1. Cooldown until time 7.
  6. Time 5: B comes off cooldown. Pop -2 (B). Execute B. Remaining: 1. Cooldown until time 8.
  7. Time 6: Idle.
  8. Time 7: A off cooldown. Execute A (last one).
  9. Time 8: B off cooldown. Execute B (last one).

Schedule: A B _ A B _ A B = 8 units.

Complexity:

  • Time: O(n * m) where n is total tasks and m is the number of unique tasks. Each time unit does at most O(log m) heap work.
  • Space: O(m) for the heap and cooldown queue.
  • The greedy strategy of always executing the most frequent available task is optimal — it minimizes idle slots.
Starter Code
import heapq
from collections import Counter

def least_interval(tasks, n):
  # Given a list of task characters and a cooldown interval n,
  # return the minimum number of time units needed to finish
  # all tasks. The same task must have at least n units of
  # cooldown between consecutive executions.
  # Tasks can be executed in any order. Idle slots are allowed.
  #
  # Example: tasks=["A","A","A","B","B","B"], n=2
  # One valid schedule: A B _ A B _ A B -> 8 units
  #
  # TODO: implement using a max-heap
  pass

# Test cases — do not modify
print(least_interval(["A","A","A","B","B","B"], 2))
print(least_interval(["A","A","A","B","B","B"], 0))
print(least_interval(["A","A","A","A","B","B","C","C"], 2))
Expected Output
8
6
8
Hints

Hint 1: Use a max-heap (negated counts) so the most frequent task is always scheduled first — this minimizes idle slots.

Hint 2: Each time unit, pop the most frequent task from the heap, decrement its count, and place it in a cooldown queue with its availability time.

Hint 3: After each time unit, check if any task in the cooldown queue is ready to re-enter the heap.

© 2026 EngineersOfAI. All rights reserved.