Job Scheduling with Deadlines in DSA Java - Build from Scratch

Job Scheduling with Deadlines

📖 Scenario: You are managing a small workshop where multiple jobs need to be completed. Each job has a deadline and a profit if completed on time. You want to schedule the jobs to maximize your total profit without missing deadlines.

🎯 Goal: Build a simple Java program that schedules jobs based on their deadlines and profits to maximize total profit. You will create the job data, set a maximum deadline, implement the scheduling logic, and print the scheduled jobs.

📋 What You'll Learn

Create an array of jobs with exact job IDs, deadlines, and profits

Create a variable for the maximum deadline

Implement the job scheduling logic to select jobs maximizing profit without missing deadlines

Print the scheduled job IDs in order of their scheduled time slots

💡 Why This Matters

🌍 Real World

Job scheduling is used in factories, computer task management, and project planning to maximize output and profits by completing tasks on time.

💼 Career

Understanding job scheduling helps in roles like software development, operations management, and systems engineering where task prioritization and resource allocation are key.

1

Create the Job Data Array

Create a class called Job with int id, int deadline, and int profit fields. Then create an array called jobs with these exact jobs: new Job(1, 4, 20), new Job(2, 1, 10), new Job(3, 1, 40), new Job(4, 1, 30).

DSA Java

// Define the Job class and create the jobs array
// Your code here

Hint

Define the Job class with the three fields and a constructor. Then create the jobs array with the exact four jobs given.

2

Set the Maximum Deadline

Create an int variable called maxDeadline and set it to 4.

DSA Java

class Job {
    int id;
    int deadline;
    int profit;

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

public class Main {
    public static void main(String[] args) {
        Job[] jobs = {
            new Job(1, 4, 20),
            new Job(2, 1, 10),
            new Job(3, 1, 40),
            new Job(4, 1, 30)
        };
        // Create maxDeadline variable here
        // Your code here
    }
}

Hint

Just create an integer variable named maxDeadline and assign it the value 4.

3

Implement Job Scheduling Logic

Sort the jobs array in descending order by profit. Then create an integer array called result of size maxDeadline initialized with -1. Use a for loop with variable i to iterate over jobs. For each job, use a for loop with variable j from Math.min(maxDeadline, jobs[i].deadline) - 1 down to 0. If result[j] is -1, assign jobs[i].id to result[j] and break the inner loop.

DSA Java

        Arrays.sort(jobs, new Comparator() {
            public int compare(Job a, Job b) {
                return b.profit - a.profit;
            }
        });
        int[] result = new int[maxDeadline];
        for (int i = 0; i = 0; j--) {
                if (result[j] == -1) {
                    result[j] = jobs[i].id;
                    break;
                }
            }
        }
        // Print scheduled jobs here

Hint

Sort jobs by profit descending. Create a result array filled with -1. For each job, try to place it in the latest free slot before its deadline.

4

Print Scheduled Job IDs

Use a for loop with variable i from 0 to maxDeadline - 1. Inside the loop, if result[i] is not -1, print result[i] followed by a space using System.out.print(result[i] + " "). After the loop, print a newline with System.out.println().

DSA Java

Hint

Loop through the result array and print each job ID that is not -1 separated by spaces. Then print a newline.

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