Job Scheduling by Deadline

How It Works

Job sequencing with deadlines schedules unit-length jobs, each with a deadline and a profit, to maximize total profit. Sort jobs by profit descending, then place each job into the latest still-free time slot at or before its deadline; if no slot is free, drop the job. Handling the most valuable jobs first and pushing them as late as possible keeps earlier slots open for tighter future deadlines, and an exchange argument shows no schedule can beat this.

With an array of slots the placement scan gives O(n^2) worst case; a disjoint-set union that jumps straight to the nearest free earlier slot brings it to near O(n log n) including the sort. This deadline-plus-value structure — sort by one key, greedily assign against the other — recurs throughout scheduling problems.

Step-by-Step Visualization

Code

static int jobScheduling(int[][] jobs) {
  Arrays.sort(jobs, (a, b) -> b[1] - a[1]); // Sort by profit desc
  int maxDeadline = 0;
  for (int[] j : jobs) maxDeadline = Math.max(maxDeadline, j[0]);
  boolean[] slots = new boolean[maxDeadline + 1];
  int profit = 0;

  for (int[] job : jobs) {
    for (int d = job[0]; d >= 1; d--) {
      if (!slots[d]) {
        slots[d] = true;
        profit += job[1];
        break;
      }
    }
  }
  return profit;
}

Tips & Gotchas

Practice Problems

• 1Maximum Profit in Job Scheduling
• 2Course Schedule III
• 3Maximum Earnings From Taxi
• 4Single-Threaded CPU

About the Task Scheduling Pattern

Assign tasks to time slots or workers to maximize value or meet deadlines. Sort by a key metric (deadline, value, ratio), then greedily assign.

Common Greedy Interview Problems

• Jump Game
• Activity Selection
• Meeting Rooms II
• Gas Station
• Candy
• Task Scheduler
• Partition Labels

Frequently Asked Questions

Other Task Scheduling Techniques