Job Sequencing — First-Free-Slot Bug Costs $50k

Job scheduling with deadlines is a classic operations research problem that appears in OS scheduling, manufacturing planning, and project management. The greedy insight — schedule highest-paying jobs as late as possible within their deadlines — is counterintuitive: you might expect to schedule early, but scheduling late preserves earlier slots for potentially higher-value jobs that might arrive.

The Union-Find optimisation that reduces O(n^2) to O(n log n) is an elegant application of the disjoint set data structure in a non-graph context — a useful demonstration that Union-Find is about more than just connected components.

Greedy Algorithm

Sort jobs by profit descending. For each job, find the latest available slot before its deadline and assign it there.

This is the core greedy choice: take the highest-profit job and defer it as late as possible. Why late? Because early slots are scarce — a job with deadline 1 can only go in slot 1. If you take a low-profit job for slot 1, you block every job with deadline 1. By scheduling high-profit jobs late, you keep earlier slots flexible for jobs that have no choice but to go early.

def job_scheduling(jobs: list[tuple]) -> tuple[int, list]:
    """
    jobs: list of (job_id, deadline, profit)
    Returns (total_profit, scheduled_job_ids)
    """
    jobs = sorted(jobs, key=lambda x: x[2], reverse=True)
    max_deadline = max(d for _, d, _ in jobs)
    slots = [None] * (max_deadline + 1)  # slots[1..max_deadline]
    total = 0
    scheduled = []
    for job_id, deadline, profit in jobs:
        # Find latest free slot at or before deadline
        for slot in range(deadline, 0, -1):
            if slots[slot] is None:
                slots[slot] = job_id
                total += profit
                scheduled.append(job_id)
                break
    return total, scheduled

jobs = [('a',2,100), ('b',1,19), ('c',2,27), ('d',1,25), ('e',3,15)]
print(job_scheduling(jobs))  # (142, ['a', 'c', 'e'])

Union-Find Optimisation — O(n log n)

The naive slot-finding is O(n) per job — O(n²) total. Using Union-Find (disjoint set), we can find the latest free slot in near-O(1) amortised time, giving O(n log n) overall.

How it works: treat each time slot as a node in a Union-Find structure. When a slot is used, union it with the slot before it (slot → slot-1). The find operation returns the largest free slot ≤ given deadline. It's essentially a 'next available lower slot' finder, with path compression making almost constant time.

def find(parent, i):
    if parent[i] != i:
        parent[i] = find(parent, parent[i])
    return parent[i]

def job_scheduling_uf(jobs):
    jobs = sorted(jobs, key=lambda x: x[2], reverse=True)
    max_d = max(d for _, d, _ in jobs)
    parent = list(range(max_d + 2))  # extra sentinel for slot 0
    total, scheduled = 0, []
    for job_id, deadline, profit in jobs:
        slot = find(parent, deadline)
        if slot > 0:
            parent[slot] = slot - 1  # union with previous slot
            total += profit
            scheduled.append(job_id)
    return total, scheduled

# Same example yields same result
jobs = [('a',2,100), ('b',1,19), ('c',2,27), ('d',1,25), ('e',3,15)]
print(job_scheduling_uf(jobs))  # (142, ['a', 'c', 'e'])

Complexity

Naive: O(n log n) sort + O(n²) slot finding = O(n²) Union-Find: O(n log n) sort + O(n α(n)) slot finding ≈ O(n log n)

For most interview purposes the naive O(n²) implementation is sufficient. But you should understand both — the interviewer may ask how to optimise when n reaches 10⁵.

Proof of Optimality via Exchange Argument

We need to prove that the greedy algorithm (highest profit first, latest slot) produces maximum total profit. The exchange argument works like this:

1. Let G be the set of jobs selected by greedy. Let O be an optimal set with maximum total profit.
2. Compare G and O from highest profit to lowest. At the first point they differ, greedy chose job j (higher profit) while optimal chose job k (lower profit or none).
3. Since j has higher profit and is scheduled at or after k's slot, we can swap k with j in O without reducing profit and without violating deadlines.
4. After a finite number of swaps, O becomes identical to G, proving G is optimal.

This argument holds only because the profit-sorted order is monotonic — the greedy never picks a lower-profit job when a higher-profit one could be placed. The 'latest slot' rule ensures we don't block future jobs unnecessarily.

Variations and Real-World Extensions

The classic job sequencing problem assumes each job takes exactly one time unit. In practice, jobs have varying durations and may depend on each other. Here are common variations:

Weighted Interval Scheduling: Jobs have start/end times and durations. Greedy fails; DP required. Job Sequencing with Release Times: Each job has a release time (earliest start). Greedy still works with slight modification — always pick the job with highest profit among available ones. Multi-Machine Scheduling: Multiple workers/CPUs. NP-hard in general; heuristic approaches used. Minimum Lateness Scheduling: Instead of maximising profit, minimise maximum lateness. Solved by EDD (Earliest Due Date) — a different greedy.

Understanding the classic version provides the foundation for these extensions.

Frequently Asked Questions