Job Scheduling with Deadlines in DSA Java

Mental Model

We want to schedule jobs so that we finish as many as possible before their deadlines, choosing the most profitable ones first.

Analogy: Imagine you have a list of tasks to do before certain times, but you can only do one task at a time. You pick the most rewarding tasks that fit before their deadlines, like fitting puzzle pieces in a limited time.

Jobs: [Job1(profit=20, deadline=2), Job2(profit=15, deadline=2), Job3(profit=10, deadline=1)]
Time slots: 1 -> 2 -> 3 -> null
Slots empty: _ -> _ -> _

Dry Run Walkthrough

Input: Jobs: [(id=1, profit=20, deadline=2), (id=2, profit=15, deadline=2), (id=3, profit=10, deadline=1)]

Goal: Schedule jobs to maximize total profit without missing deadlines

Step 1: Sort jobs by profit descending

Jobs sorted: [Job1(20,2), Job2(15,2), Job3(10,1)]

Why: We want to pick the most profitable jobs first to maximize profit

Step 2: Schedule Job1 at latest available slot before deadline 2

Time slots: _ -> [Job1] -> _

Why: Slot 2 is free and within deadline, so assign Job1 there

Step 3: Schedule Job2 at latest available slot before deadline 2

Time slots: [Job2] -> [Job1] -> _

Why: Slot 2 is taken, try slot 1 which is free and before deadline

Step 4: Try to schedule Job3 before deadline 1

Time slots: [Job2] -> [Job1] -> _

Why: Slot 1 is taken, no free slot before deadline, skip Job3

Result:

Scheduled jobs: [Job2] -> [Job1] -> _
Total profit: 35

Annotated Code

DSA Java

import java.util.*;

class Job {
    int id, deadline, profit;
    Job(int id, int deadline, int profit) {
        this.id = id;
        this.deadline = deadline;
        this.profit = profit;
    }
}

public class JobScheduling {
    public static int[] scheduleJobs(Job[] jobs) {
        Arrays.sort(jobs, (a, b) -> b.profit - a.profit); // sort by profit desc
        int maxDeadline = 0;
        for (Job job : jobs) {
            if (job.deadline > maxDeadline) maxDeadline = job.deadline;
        }
        int[] result = new int[maxDeadline + 1]; // slot 0 unused
        Arrays.fill(result, -1); // -1 means free slot
        int totalProfit = 0;
        int count = 0;
        for (Job job : jobs) {
            for (int slot = job.deadline; slot > 0; slot--) {
                if (result[slot] == -1) {
                    result[slot] = job.id;
                    totalProfit += job.profit;
                    count++;
                    break; // job scheduled
                }
            }
        }
        System.out.print("Scheduled job IDs in slots: ");
        for (int i = 1; i <= maxDeadline; i++) {
            if (result[i] != -1) System.out.print(result[i] + " ");
            else System.out.print("_ ");
        }
        System.out.println();
        System.out.println("Total profit: " + totalProfit);
        return new int[]{count, totalProfit};
    }

    public static void main(String[] args) {
        Job[] jobs = {
            new Job(1, 2, 20),
            new Job(2, 2, 15),
            new Job(3, 1, 10)
        };
        scheduleJobs(jobs);
    }
}

Arrays.sort(jobs, (a, b) -> b.profit - a.profit);

sort jobs by descending profit to prioritize high profit jobs

for (int slot = job.deadline; slot > 0; slot--) {

try to find latest free slot before job deadline

if (result[slot] == -1) {

check if slot is free to schedule job

result[slot] = job.id;

assign job to slot

totalProfit += job.profit;

accumulate profit for scheduled jobs

break;

stop searching slots once job is scheduled

Output

Scheduled job IDs in slots: 2 1 

Total profit: 35

Complexity Analysis

Time: O(n log n) because we sort the jobs by profit and then for each job we try to find a slot up to its deadline

Space: O(d) where d is the maximum deadline, for the slots array to track scheduled jobs

vs Alternative: Naive approach tries all permutations which is factorial time; this greedy method is efficient and practical

Edge Cases

No jobs

No scheduling happens, output shows empty slots and zero profit

DSA Java

for (Job job : jobs) { ... } handles empty array gracefully

All jobs have the same deadline

Only the most profitable jobs fitting in available slots are scheduled

DSA Java

for (int slot = job.deadline; slot > 0; slot--) { ... } tries slots before deadline

Jobs with deadlines exceeding max deadline

Slots array sized to max deadline ensures no out-of-bound errors

DSA Java

int maxDeadline = 0; for (Job job : jobs) { if (job.deadline > maxDeadline) maxDeadline = job.deadline; }

When to Use This Pattern

When you see tasks with deadlines and profits and need to maximize profit by scheduling, use the greedy job scheduling pattern to pick highest profit jobs fitting deadlines.

Common Mistakes

Mistake: Scheduling jobs in order without sorting by profit
Fix: Sort jobs by descending profit first to ensure maximum profit scheduling

Mistake: Assigning jobs to earliest slot instead of latest slot before deadline
Fix: Try slots from job.deadline down to 1 to maximize slot usage

Summary

Schedules jobs to maximize total profit without missing deadlines.

Use when you have tasks with deadlines and profits and want to maximize earnings.

Sort jobs by profit and assign each to the latest free slot before its deadline.

Practice

1. What is the main goal of the Job Scheduling with Deadlines problem?

easy

A. Maximize the number of jobs scheduled regardless of profit

B. Minimize the number of jobs scheduled

C. Schedule jobs in the order they appear without considering deadlines

D. Maximize the total profit by scheduling jobs before their deadlines

Solution

1. Step 1: Understand the problem objective

   The problem aims to schedule jobs so that each job finishes before its deadline to earn profit.

2. Step 2: Identify the optimization goal

   We want to maximize total profit, not just count or order jobs.

3. Final Answer:

   Maximize the total profit by scheduling jobs before their deadlines -> Option D

4. Quick Check:

   Goal = Maximize profit [OK]

Hint: Focus on maximizing profit within deadlines [OK]

Common Mistakes:

• Thinking it's about scheduling all jobs
• Ignoring profit values
• Scheduling jobs without deadline checks

2. Which of the following Java code snippets correctly sorts an array of jobs by their profit in descending order?

easy

A. Arrays.sort(jobs, (a, b) -> a.profit - b.profit);

B. Arrays.sort(jobs, Comparator.comparingInt(j -> j.deadline));

C. Arrays.sort(jobs, (a, b) -> b.profit - a.profit);

D. Arrays.sort(jobs);

Solution

1. Step 1: Identify sorting by profit descending

   To sort descending by profit, compare b.profit - a.profit.

2. Step 2: Check lambda syntax correctness

   Arrays.sort(jobs, (a, b) -> b.profit - a.profit); uses (a, b) -> b.profit - a.profit which sorts descending.

3. Final Answer:

   Arrays.sort(jobs, (a, b) -> b.profit - a.profit); -> Option C

4. Quick Check:

   Descending profit sort = Arrays.sort(jobs, (a, b) -> b.profit - a.profit); [OK]

Hint: Use (b.profit - a.profit) for descending sort [OK]

Common Mistakes:

• Using a.profit - b.profit for descending order
• Sorting by deadline instead of profit
• Using default sort without comparator

3. Given the following jobs with (id, deadline, profit):
Job[] jobs = { new Job('a', 2, 100), new Job('b', 1, 19), new Job('c', 2, 27), new Job('d', 1, 25), new Job('e', 3, 15) };
What is the maximum profit achievable by scheduling these jobs before their deadlines?

medium

A. 142

B. 185

C. 100

D. 115

Solution

1. Step 1: Sort jobs by profit descending

   Sorted: a(100,2), d(25,1), c(27,2), b(19,1), e(15,3)

2. Step 2: Schedule jobs greedily before deadlines

   Schedule 'a' at slot 2, 'c' at slot 1 (slot 2 taken), 'e' at slot 3. Total profit = 100 + 27 + 15 = 142.

3. Final Answer:

   142 -> Option A

4. Quick Check:

   Profit sum = 142 [OK]

Hint: Schedule highest profit jobs first in latest free slot [OK]

Common Mistakes:

• Scheduling jobs without sorting by profit
• Overlapping jobs in same slot
• Ignoring deadlines

4. Identify the error in the following Java code snippet for job scheduling:

Arrays.sort(jobs, (a, b) -> a.profit - b.profit);
boolean[] slot = new boolean[maxDeadline + 1];
for (Job job : jobs) {
  for (int j = job.deadline; j > 0; j--) {
    if (!slot[j]) {
      slot[j] = true;
      totalProfit += job.profit;
      break;
    }
  }
}

medium

A. Sorting should be in descending order of profit

B. Slot array size should be maxDeadline, not maxDeadline + 1

C. Inner loop should run from 1 to job.deadline, not backward

D. No error, code is correct

Solution

1. Step 1: Check sorting order

   Sorting by a.profit - b.profit sorts ascending, but we need descending to maximize profit.

2. Step 2: Verify scheduling logic

   The slot array and inner loop correctly find latest free slot before deadline.

3. Final Answer:

   Sorting should be in descending order of profit -> Option A

4. Quick Check:

   Profit descending sort needed [OK]

Hint: Sort jobs by profit descending to maximize total profit [OK]

Common Mistakes:

• Sorting ascending by profit
• Incorrect slot array size off by one
• Loop direction confusion

5. You have jobs with deadlines and profits:
Job[] jobs = { new Job('x', 4, 70), new Job('y', 1, 80), new Job('z', 1, 30), new Job('w', 2, 100), new Job('v', 3, 40) };
Using the job scheduling algorithm, which jobs will be scheduled to maximize profit and what is the total profit?

hard

A. Jobs w, y, x scheduled; Total profit = 250

B. Jobs y, w, v, x scheduled; Total profit = 290

C. Jobs y, w, x scheduled; Total profit = 250

D. Jobs y, w, v scheduled; Total profit = 220

Solution

1. Step 1: Sort jobs by profit descending

   Sorted: w(100,2), y(80,1), x(70,4), v(40,3), z(30,1)

2. Step 2: Schedule jobs greedily in latest free slot before deadline

   Schedule y at slot 1, w at slot 2, v at slot 3, x at slot 4. z cannot be scheduled (slot 1 taken). Total profit = 80+100+40+70=290.

3. Final Answer:

   Jobs y, w, v, x scheduled; Total profit = 290 -> Option B

4. Quick Check:

   Profit sum = 290 [OK]

Hint: Schedule highest profit jobs in latest free slots first [OK]

Common Mistakes:

• Scheduling jobs ignoring deadlines
• Not choosing latest free slot
• Missing highest profit jobs