Deadline Scheduling Greedy

Description

Jobs each take one unit of time, have a deadline and pay a profit only if finished by it. With one machine, which jobs should run, and when? Trying every subset and order is hopeless; two greedy rules together solve it exactly.

This skill covers the two rules, most profitable first and each job in its latest free slot. It also covers the "accept, then drop the worst" form that handles jobs of different lengths, and how to find free slots quickly when deadlines are large.

We'll go from simple to more technical:

1. The pattern: profit order picks which jobs run, and the latest free slot picks when.
2. A second flavor: sort by deadline, accept, and drop the worst from a heap (Course Schedule III).
3. Where deadline scheduling shows up (batch windows, deliverables, admission control).
4. What breaks it: earliest slots, deadline-only order, slow slot scans, durations with profits.

The approach

int[] jobSequencing(int[] deadlines, int[] profits) {
    Integer[] order = new Integer[deadlines.length];
    for (int i = 0; i < order.length; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> Integer.compare(profits[b], profits[a]));   // most profitable first
    int maxDeadline = Arrays.stream(deadlines).max().getAsInt();
    boolean[] taken = new boolean[maxDeadline + 1];                           // slots 1..maxDeadline
    int count = 0, total = 0;
    for (int i : order) {
        for (int slot = deadlines[i]; slot >= 1; slot--) {                   // latest free slot first
            if (!taken[slot]) {
                taken[slot] = true;
                count++;
                total += profits[i];
                break;
            }
        }
    }
    return new int[]{count, total};
}

def job_sequencing(deadlines: list[int], profits: list[int]) -> list[int]:
    max_deadline = max(deadlines)
    taken = [False] * (max_deadline + 1)                     # slots 1..max_deadline
    count = total = 0
    for p, d in sorted(zip(profits, deadlines), reverse=True):   # most profitable first
        for slot in range(d, 0, -1):                         # latest free slot first
            if not taken[slot]:
                taken[slot] = True
                count += 1
                total += p
                break
    return [count, total]

Profit order decides which jobs to keep; the latest-slot rule decides where to put them. Placing a job as late as its deadline allows keeps early slots free for jobs with tighter deadlines. The earliest free slot fails: with deadlines [2, 1] and profits [100, 50], the 100-job takes slot 1 and the 50-job has nowhere to go - 100 instead of 150.

The inner scan is the weak point: when many deadlines are large, each placement can walk past many taken slots - about 5 * 10^9 steps for 10^5 jobs all due at time 10^5. A union-find "next free slot at or before d" (after using slot s, link it to s - 1) makes each placement nearly O(1).

A second flavor: accept, then drop the worst (greedy with regret)

Sort by deadline instead and keep a heap of what you've accepted. Take each job tentatively; if you now hold more jobs than the deadline allows, drop the least profitable one. For jobs with different durations - Course Schedule III: take the most courses, each with a duration and a last day - the same idea drops the longest course:

int scheduleCourse(int[][] courses) {                     // each course is [duration, lastDay]
    Arrays.sort(courses, (a, b) -> Integer.compare(a[1], b[1]));   // by last day
    PriorityQueue<Integer> taken = new PriorityQueue<>(Comparator.reverseOrder());   // longest on top
    int time = 0;
    for (int[] c : courses) {
        time += c[0];
        taken.add(c[0]);
        if (time > c[1]) time -= taken.poll();           // over the deadline: drop the longest course
    }
    return taken.size();
}

import heapq


def schedule_course(courses: list[list[int]]) -> int:        # each course is [duration, last_day]
    taken = []                                   # heapq is a min-heap: store -duration for "longest on top"
    time = 0
    for duration, last_day in sorted(courses, key=lambda c: c[1]):   # by last day
        time += duration
        heapq.heappush(taken, -duration)
        if time > last_day:
            time += heapq.heappop(taken)         # over the deadline: drop the longest course
    return len(taken)

Dropping the longest accepted course restores feasibility while giving back the most time, and the count is never worse than skipping the current course. Simply skipping a course that doesn't fit is wrong: courses [5, 5], [4, 6], [2, 6] fit 2 (the last two), but skipping keeps [5, 5] and fits only 1. In Python, heapq's heappush/heappop are a min-heap, so push -duration and negate what you pop - forgetting drops the shortest course instead (Python 3.14 adds heapq.heappush_max/heappop_max; negating works on every version).

Where you'll see it

Scheduling paid batch jobs into a fixed number of nightly windows, choosing which deliverables fit before their due dates, and admission control ("accept the request, and if the queue can't meet its deadlines, evict the least valuable one") all use these two greedy forms.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why does each job go into its latest free slot rather than its earliest?

2. In Course Schedule III, why drop the longest course taken so far instead of skipping the current one?

3. What does union-find speed up in job sequencing?

Key takeaways

• Unit jobs: highest profit first, each into its latest free slot at or before its deadline.
• Earliest-slot placement and deadline-only order both fail.
• Union-find finds free slots fast; the naive scan is O(n * maxDeadline).
• Greedy with regret: sort by deadline, accept, and drop the worst from a heap when a deadline breaks.