Activity Selection and Job Sequencing
28 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Many scheduling problems ask for the most work that fits without clashes. The right greedy key is the one that leaves the most room for what comes next. This lesson shows two classic problems and the proof behind them.
Activity selection: sort by finish time
Activity selection asks for the largest set of requests that do not overlap in time. Sorting by finish time and taking each request that fits gives an optimal answer.
A hall has many booking requests, each with a start and an end. Choose the largest number of bookings that do not overlap. Sort by end time and take each request that starts after the last one ended.
def max_bookings(bookings): chosen = [] last_end = float("-inf") for start, end in sorted(bookings, key=lambda b: b[1]): if start >= last_end: chosen.append((start, end)) last_end = end return chosen
print(max_bookings([(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (8, 11)]))Example 1 · Brute force: try every subset of bookings
from itertools import combinations
bookings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (8, 11)]
def clash_free(group): ordered = sorted(group) return all(a[1] <= b[0] for a, b in zip(ordered, ordered[1:]))
best = 0for size in range(len(bookings) + 1): for group in combinations(bookings, size): if clash_free(group): best = max(best, size)print(best)3
What this code does
- It checks all 2 to the power n subsets, so it takes O(2 to the power n) time. It is only useful to confirm a faster answer on tiny inputs.
- The best size is 3, which the greedy version must also find.
Example 2 · Greedy by earliest finish
bookings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (8, 11)]last_end = 0count = 0for start, end in sorted(bookings, key=lambda b: b[1]): if start >= last_end: count += 1 last_end = endprint(count)3
What this code does
- Sorted by end, the bookings are (1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (8, 11). The scan takes (1, 4), (5, 7) and (8, 11).
- It matches the brute force in O(n log n) instead of O(2 to the power n).
Sorting costs O(n log n) and the scan costs O(n). A booking that ends at the same minute another starts is allowed here.
Why the earliest finish is the right key
The request that ends first leaves the most free time after it. Any best answer can swap its first request for this one without losing a request. That is the exchange argument.
- Earliest start fails: one long request that starts first can block many short ones.
- Shortest length fails: a short request in the middle can overlap two others that fit together.
- Earliest finish works: it never blocks more than any other first choice would.
- Always test your key on a tiny input that tries to break it.
Example 3 · Wrong keys: shortest length fails here
bookings = [(1, 5), (4, 6), (5, 9)]
def pick(items, key): count, last_end = 0, 0 for start, end in sorted(items, key=key): if start >= last_end: count += 1 last_end = end return count
print(pick(bookings, lambda b: b[1]))print(pick(bookings, lambda b: b[1] - b[0]))2 1
What this code does
- The first line sorts by finish time and gets 2 bookings, (1, 5) and (5, 9).
- The second sorts by length, takes (4, 6) first, and blocks both others, so it gets only 1.
Job sequencing with deadlines
Job sequencing schedules unit-time jobs, each with a deadline and a profit, so that the total profit of the jobs finished on time is as large as possible.
Each job takes one hour, has a deadline hour and earns a profit. Only one job runs per hour. Try jobs from the highest profit and put each one in the latest free hour on or before its deadline.
def best_profit(jobs): last = max(deadline for deadline, _ in jobs) slot = [None] * (last + 1) total = 0 for deadline, profit in sorted(jobs, key=lambda j: -j[1]): for hour in range(deadline, 0, -1): if slot[hour] is None: slot[hour] = profit total += profit break return total
print(best_profit([(2, 100), (1, 19), (2, 27), (1, 25), (3, 15)]))Example 4 · Job sequencing, with the hours shown
jobs = [(2, 100), (1, 19), (2, 27), (1, 25), (3, 15)]slot = [None] * 4for deadline, profit in sorted(jobs, key=lambda j: -j[1]): for hour in range(deadline, 0, -1): if slot[hour] is None: slot[hour] = profit breakprint(slot[1:])print(sum(p for p in slot if p))[27, 100, 15] 142
What this code does
- The 100 job takes hour 2. The 27 job finds hour 2 taken and takes hour 1. The 25 and 19 jobs find no free hour, and the 15 job takes hour 3.
- Placing a job in the latest free hour keeps early hours open for jobs with tight deadlines.
The inner loop can run up to n times, so this version is O(n squared) in the worst case but is easy to write and explain.
A faster version with a heap
A min-heap is a structure that always gives its smallest value first. In Python, heapq keeps a list as a min-heap, and push and pop cost O(log n).
Sort jobs by deadline and keep a min-heap of the profits you accepted. If the heap grows bigger than the deadline allows, drop the smallest profit.
import heapq
def best_profit_fast(jobs): heap = [] for deadline, profit in sorted(jobs): heapq.heappush(heap, profit) if len(heap) > deadline: heapq.heappop(heap) return sum(heap)
print(best_profit_fast([(2, 100), (1, 19), (2, 27), (1, 25), (3, 15)]))Example 5 · Same answer with a min-heap
import heapq
jobs = [(2, 100), (1, 19), (2, 27), (1, 25), (3, 15)]heap = []for deadline, profit in sorted(jobs): heapq.heappush(heap, profit) if len(heap) > deadline: heapq.heappop(heap)print(sorted(heap), sum(heap))[15, 27, 100] 142
What this code does
- After sorting by deadline, the heap size can never be more than the current deadline, or one job would miss it.
- When the heap is too big, the smallest profit is dropped. This is O(n log n).
Each job is pushed and popped at most once, so the time is O(n log n) and the space is O(n).
Next step
Check your understanding
10 quick questions