Greedy Algorithms6 min read

Task Scheduling

Do homework by closest deadline first — miss nothing, earn the most
time:Fast · \(O(n \log n)\)space:Linear · \(O(n)\)key insight:Sort by profit; use Union-Find for free-slot lookup

It's Sunday night and you have a pile of homework. Each assignment earns you points if you turn it in by its deadline, and each takes exactly one hour. You can only work on one at a time. Which ones do you do?

If you're smart about it: grab the most valuable homework first. Schedule it in the latest available slot before its deadline (so you leave earlier slots open for other tasks). Skip anything that no longer has a free slot.

That's task scheduling with deadlines in one paragraph. The trick is making that "find the latest free slot" step fast.

Formalising the Problem

You have n unit-time tasks (each takes exactly 1 time slot). Task i has:
• deadline d_i — must be completed in time slot 1..d_i
• profit p_i — earned only if completed by its deadline

You can execute at most one task per slot. Goal: choose which tasks to run to maximize total profit.

The Greedy Strategy

1. Sort tasks by profit descending.
2. For each task (in profit order), find the latest free slot at or before its deadline.
3. If a free slot exists, assign the task to that slot and mark the slot used.
4. If no free slot, skip the task.

Assigning to the latest available slot (rather than the earliest) is deliberate — it keeps earlier slots open for future high-profit tasks that might have tighter deadlines.

Fast Slot Lookup with Union-Find

The naive approach: for each task, scan backwards from its deadline until you find a free slot. That's \(O(n)\) per task, \(O(n^2)\) total — too slow.

The smart approach: maintain a Union-Find (disjoint set) structure where parent[t] points to the latest free slot ≤ t. When slot t is used, union(t, t−1) so future queries for ≤ t automatically skip to the next available slot. Each query takes near-\(O(1)\) amortized time (inverse Ackermann function). Total: \(O(n \log n)\) for the sort, \(O(nα(n)\)) for the scheduling — sort dominates.

Why Greedy Is Correct — Matroid Theory

The collection of all feasible task sets (sets that can all be completed on time) forms a matroid. For any weighted matroid, the greedy algorithm — sort by weight descending, add an element if the set remains independent — finds the maximum-weight independent set. This is the deep theoretical reason greedy works here: feasibility has exactly the structure of matroid independence.

Key Feasibility Check

A set of tasks S is feasible if and only if for every time t, the number of tasks in S with deadline ≤ t is at most t. Intuitively: you can't do more tasks than time slots exist up to any deadline. This condition can be checked efficiently with Union-Find.

Note: Always assign a task to the latest available slot before its deadline — not the earliest. This keeps earlier slots free for tasks with tighter deadlines that you'll encounter later in the sorted order.

Task Scheduling — Greedy with Union-Find

def task_scheduling(tasks):
    # tasks: list of (profit, deadline)
    tasks.sort(reverse=True)  # sort by profit descending
    if not tasks: return 0, []
    max_deadline = max(d for _, d in tasks)
    # Union-Find: parent[t] = latest free slot <= t
    parent = list(range(max_deadline + 1))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x
    total = 0
    schedule = []
    for profit, deadline in tasks:
        slot = find(deadline)
        if slot > 0:  # slot 0 is a sentinel (no free slot)
            schedule.append((slot, profit, deadline))
            total += profit
            parent[slot] = slot - 1  # union: next query skips this slot
    schedule.sort()
    return total, schedule


tasks = [(100, 2), (90, 1), (80, 2), (70, 1)]
total, sched = task_scheduling(tasks)
print(f"Max profit: {total}")
for slot, profit, deadline in sched:
    print(f"  Slot {slot}: profit={profit}, deadline={deadline}")
Output
Max profit: 190
  Slot 1: profit=90, deadline=1
  Slot 2: profit=100, deadline=2

Complexity

📊 Sort by profit descendingDominant cost — greedy processes tasks in profit order
One-time sort\(O(n \log n)\)
🐢 Naive slot lookupScan backwards from deadline for each task — too slow
Per task scan\(O(n)\) per task → \(O(n^2)\) total
⚡ Union-Find slot lookupPath compression finds the latest free slot in near-\(O(1)\)
Near-constant per query\(O(α(n)\)) amortized
🏁 Total with Union-FindSort once + n near-\(O(1)\) Union-Find operations
Sort dominates\(O(n \log n)\)
📦 SpaceUnion-Find parent array sized to maximum deadline
Linear\(O(n)\)

Quick check

Tasks: (profit=100, deadline=2), (profit=90, deadline=1), (profit=80, deadline=2), (profit=70, deadline=1). What is the maximum achievable profit?

Continue reading

Interval Scheduling
Book as many non-overlapping meetings as possible — always pick the one that ends earliest
→
Greedy Pattern
Always grab the biggest slice of pizza — sometimes that's optimal, sometimes it isn't
→