Always take the most urgent thing

A heap plus a waiting area, which is the shape of nearly every scheduling problem.

Why it works

Why taking the most urgent is safe

The greedy choice is to always run whatever is most pressing among the currently available options. For problems where every item takes the same time and delay is what you are minimizing, that is provably optimal by an exchange argument like the one in U6.

It is not automatically right for every scheduling problem. When items have different durations, or when future arrivals change what is best, greedy can fail. Check that the exchange argument holds before assuming it.

Here is a single tick in isolation: two tasks with three runs each, one of them chosen and parked until it is allowed to run again.

1import heapq2from collections import deque3 4available = [-3, -3]                 # remaining counts, negated for a max-heap5heapq.heapify(available)6waiting = deque()                    # (ready_time, remaining_count)7cooldown = 28time = 19 10remaining = heapq.heappop(available) + 1        # ran one, so one fewer11print("just ran a task with", -remaining, "left")12if remaining != 0:13    waiting.append((time + cooldown + 1, remaining))14 15print("available:", available)16print("waiting:", list(waiting))

Negation is what makes heapq hand back the task with the most left to do.

Predict the output· 5 min

Predict the output: a max-heap out of a min-heap

heapq only ever gives back the smallest item. The counts here are negated so that the largest one surfaces. Type the three lines it prints.

Python

1import heapq2 3remaining = {"a": 3, "b": 1, "c": 2}4 5heap = [-count for count in remaining.values()]6heapq.heapify(heap)7print(heap[0], "is on top")8 9taken = heapq.heappop(heap)10print("popped", taken, "which means a real count of", -taken)11 12heapq.heappush(heap, taken + 1)          # ran it once, so one fewer13print(sorted(-value for value in heap))

Printed output

Problem· 28 min

Task Scheduler

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1import heapq2from collections import deque3 4available = [-3, -3] # remaining counts, negated for a max-heap5heapq.heapify(available)6waiting = deque() # (ready_time, remaining_count)7cooldown = 28time = 19 10remaining = heapq.heappop(available) + 1 # ran one, so one fewer11print("just ran a task with", -remaining, "left")12if remaining != 0:13 waiting.append((time + cooldown + 1, remaining))14 15print("available:", available)16print("waiting:", list(waiting))

1import heapq2 3remaining = {"a": 3, "b": 1, "c": 2}4 5heap = [-count for count in remaining.values()]6heapq.heapify(heap)7print(heap[0], "is on top")8 9taken = heapq.heappop(heap)10print("popped", taken, "which means a real count of", -taken)11 12heapq.heappush(heap, taken + 1) # ran it once, so one fewer13print(sorted(-value for value in heap))