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.

The Greedy Bet: Maximizing Profit Under Deadline Pressure

Job sequencing with deadlines is a classic greedy optimization: given a set of jobs, each with a deadline and profit, schedule them on a single machine to maximize total profit. The core mechanic is simple — sort jobs by profit descending, then assign each job to the latest available slot before its deadline. This works because profit is additive and deadlines are uniform time units; the greedy choice of highest profit first is optimal when all jobs take unit time.

In practice, the algorithm runs in O(n log n) due to sorting, then O(n * m) for slot assignment where m is the max deadline. The key property: it exploits the fact that any job can be scheduled in any free slot ≤ its deadline. The first-free-slot (or latest-free-slot) variant is critical — assigning a job to the earliest free slot can break optimality, while the latest free slot preserves room for higher-profit jobs with tighter deadlines.

Use this when you have unit-time tasks, independent jobs, and a single resource. It appears in cloud batch schedulers, real-time task dispatchers, and even ad slot allocation. The greedy fails if jobs have varying durations or dependencies — then you need weighted interval scheduling or topological ordering. In production, the difference between earliest-slot and latest-slot assignment is the difference between a working scheduler and a $50k revenue loss.

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.

The Naive Way: Sorting + Slot-Scanning in O(n²)

Before you reach for Union-Find or a heap, understand why the naive approach is your first mental model and your last choice in production.

Sort jobs by descending profit. Then for each job, scan backwards from its deadline looking for a free slot. Assign the job to the latest free slot ≤ its deadline. That's it. Simple, correct, and O(n²) in the worst case — because for each job you might scan up to d time slots where d is the maximum deadline.

Why does this matter? With 10 jobs it's instant. With 100,000 jobs and a max deadline of 10,000, you're scanning up to a billion slot-checks. That's not just slow — it's a ticket to pager duty. The naive approach teaches you the core logic: deadline = latest possible start, and profit sorting ensures you don't waste expensive slots on cheap jobs. Understand it, then discard it for anything larger than a coding interview.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class NaiveJobScheduler {
    static class Job {
        int id, deadline, profit;
        Job(int i, int d, int p) { id = i; deadline = d; profit = p; }
    }

    public static int[] scheduleMaxProfit(List<Job> jobs) {
        jobs.sort((a, b) -> b.profit - a.profit);
        int maxDeadline = jobs.stream().mapToInt(j -> j.deadline).max().orElse(0);
        int[] slots = new int[maxDeadline + 1]; // 0 = free
        int count = 0, totalProfit = 0;

        for (Job job : jobs) {
            for (int t = job.deadline; t > 0; t--) {
                if (slots[t] == 0) {
                    slots[t] = job.id;
                    count++;
                    totalProfit += job.profit;
                    break;
                }
            }
        }
        return new int[]{count, totalProfit};
    }

    public static void main(String[] args) {
        List<Job> jobs = Arrays.asList(
            new Job(1, 4, 20), new Job(2, 1, 10),
            new Job(3, 1, 40), new Job(4, 1, 30));
        int[] result = scheduleMaxProfit(jobs);
        System.out.println("Jobs done: " + result[0] + ", Profit: " + result[1]);
    }
}

Heap-Optimised: O(n log n) with a Min-Priority Queue

The naive approach scans slots linearly. The heap approach eliminates that scan entirely by processing jobs in deadline order and maintaining a min-heap of selected profits.

Sort jobs by deadline ascending. Iterate through the sorted jobs, adding each profit to a min-heap. If the heap size exceeds the current deadline (you have more jobs than time slots), pop the smallest profit. The heap always holds the most profitable jobs that fit within the deadlines seen so far.

This works because any job with deadline d can be scheduled in any of the d slots. By sorting by deadline, you build up the set of candidates gradually. The min-heap prunes the weakest profit when you run out of slots. At the end, the heap contains the optimal selection. Total time: O(n log n) due to heap operations. Space: O(n) for the heap.

This is the version most interviewers expect and most production code uses when you don't have Union-Find infrastructure handy. It's simpler to implement than DSU and performs well for tens of thousands of jobs.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class HeapJobScheduler {
    static class Job {
        int deadline, profit;
        Job(int d, int p) { deadline = d; profit = p; }
    }

    public static int scheduleMaxProfit(List<Job> jobs) {
        jobs.sort(Comparator.comparingInt(j -> j.deadline));
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (Job job : jobs) {
            minHeap.offer(job.profit);
            if (minHeap.size() > job.deadline) {
                minHeap.poll(); // drop weakest profit
            }
        }

        return minHeap.stream().mapToInt(Integer::intValue).sum();
    }

    public static void main(String[] args) {
        List<Job> jobs = Arrays.asList(
            new Job(4, 20), new Job(1, 10),
            new Job(1, 40), new Job(1, 30));
        System.out.println("Max profit: " + scheduleMaxProfit(jobs));
    }
}