Job Scheduling with Deadlines in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Job Scheduling with Deadlines and Profits

What is the output of the following Java code that schedules jobs to maximize profit given deadlines?

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 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)
        };
        Arrays.sort(jobs, (a, b) -> b.profit - a.profit);
        int n = jobs.length;
        int maxDeadline = 0;
        for (Job job : jobs) {
            if (job.deadline > maxDeadline) maxDeadline = job.deadline;
        }
        int[] result = new int[maxDeadline + 1];
        Arrays.fill(result, -1);
        int count = 0, profit = 0;
        for (Job job : jobs) {
            for (int j = job.deadline; j > 0; j--) {
                if (result[j] == -1) {
                    result[j] = job.id;
                    count++;
                    profit += job.profit;
                    break;
                }
            }
        }
        System.out.println("Jobs scheduled: " + count);
        System.out.println("Total profit: " + profit);
    }
}

A

Jobs scheduled: 2
Total profit: 60

B

Jobs scheduled: 3
Total profit: 90

C

Jobs scheduled: 1
Total profit: 40

D

Jobs scheduled: 4
Total profit: 100

💡 Hint

Sort jobs by profit descending and assign each job to the latest available slot before its deadline.

The jobs are sorted by profit: Job 3 (40), Job 4 (30), Job 1 (20), Job 2 (10). Job 3 is scheduled at slot 1, Job 4 cannot be scheduled at slot 1 (taken), so skipped, Job 1 is scheduled at slot 4, Job 2 cannot be scheduled (slot 1 taken). Total jobs scheduled = 2, total profit = 40 + 20 = 60 (option A).

❓ Predict Output

intermediate

Output of Job Scheduling with Overlapping Deadlines

What is the output of this Java code that schedules jobs with overlapping deadlines to maximize profit?

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 Main {
    public static void main(String[] args) {
        Job[] jobs = {
            new Job(1, 2, 100),
            new Job(2, 1, 19),
            new Job(3, 2, 27),
            new Job(4, 1, 25),
            new Job(5, 3, 15)
        };
        Arrays.sort(jobs, (a, b) -> b.profit - a.profit);
        int n = jobs.length;
        int maxDeadline = 0;
        for (Job job : jobs) {
            if (job.deadline > maxDeadline) maxDeadline = job.deadline;
        }
        int[] result = new int[maxDeadline + 1];
        Arrays.fill(result, -1);
        int count = 0, profit = 0;
        for (Job job : jobs) {
            for (int j = job.deadline; j > 0; j--) {
                if (result[j] == -1) {
                    result[j] = job.id;
                    count++;
                    profit += job.profit;
                    break;
                }
            }
        }
        System.out.println("Jobs scheduled: " + count);
        System.out.println("Total profit: " + profit);
    }
}

A

Jobs scheduled: 5
Total profit: 186

B

Jobs scheduled: 4
Total profit: 171

C

Jobs scheduled: 2
Total profit: 125

D

Jobs scheduled: 3
Total profit: 142

💡 Hint

Assign jobs starting from highest profit to latest available slot before deadline.

Jobs sorted by profit: 1(100), 3(27), 4(25), 2(19), 5(15). Schedule Job 1 at slot 2, Job 3 at slot 1, Job 4 cannot be scheduled (slot 1 taken), Job 2 cannot be scheduled (slot 1 taken), Job 5 at slot 3. So 3 jobs scheduled with total profit 100+27+15=142.

🔧 Debug

advanced

Identify the bug in Job Scheduling code

The following Java code is intended to schedule jobs to maximize profit given deadlines. It compiles but produces incorrect output. What is the bug?

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 Main {
    public static void main(String[] args) {
        Job[] jobs = {
            new Job(1, 2, 100),
            new Job(2, 1, 19),
            new Job(3, 2, 27),
            new Job(4, 1, 25),
            new Job(5, 3, 15)
        };
        Arrays.sort(jobs, (a, b) -> a.profit - b.profit);
        int n = jobs.length;
        int maxDeadline = 0;
        for (Job job : jobs) {
            if (job.deadline > maxDeadline) maxDeadline = job.deadline;
        }
        int[] result = new int[maxDeadline + 1];
        Arrays.fill(result, -1);
        int count = 0, profit = 0;
        for (Job job : jobs) {
            for (int j = job.deadline; j > 0; j--) {
                if (result[j] == -1) {
                    result[j] = job.id;
                    count++;
                    profit += job.profit;
                    break;
                }
            }
        }
        System.out.println("Jobs scheduled: " + count);
        System.out.println("Total profit: " + profit);
    }
}

A Jobs are sorted in ascending order of profit instead of descending order.

B The inner loop should run from 1 to job.deadline instead of job.deadline to 1.

C The array 'result' is not initialized properly with -1 values.

D The profit is not accumulated correctly inside the loop.

💡 Hint

Check the sorting order of jobs by profit.

The code sorts jobs by ascending profit (a.profit - b.profit), so low profit jobs are scheduled first, which is incorrect. It should be descending order (b.profit - a.profit) to maximize profit.

🧠 Conceptual

advanced

Maximum number of jobs scheduled with deadlines

Given a list of jobs with deadlines and profits, what is the maximum number of jobs that can be scheduled if each job takes exactly 1 unit of time and no two jobs can be scheduled at the same time?

A The total number of jobs given in the list.

B The maximum deadline among all jobs.

C The minimum deadline among all jobs.

D The sum of all deadlines.

💡 Hint

Think about the time slots available to schedule jobs.

Since each job takes 1 unit time and no overlap allowed, the maximum jobs scheduled cannot exceed the maximum deadline (time slots available).

🚀 Application

expert

Find the scheduled jobs and total profit

Given the following jobs with id, deadline, and profit, which jobs will be scheduled and what is the total profit after applying the job scheduling algorithm?

DSA Java

Job[] jobs = {
    new Job(1, 2, 50),
    new Job(2, 1, 10),
    new Job(3, 2, 20),
    new Job(4, 1, 30),
    new Job(5, 3, 40),
    new Job(6, 2, 60)
};

A Scheduled jobs: 1, 4, 5; Total profit: 120

B Scheduled jobs: 6, 3, 5; Total profit: 120

C Scheduled jobs: 6, 1, 5; Total profit: 150

D Scheduled jobs: 6, 4, 5; Total profit: 130

💡 Hint

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

Jobs sorted by profit: 6(60),1(50),5(40),4(30),3(20),2(10). Schedule Job 6 at slot 2, Job 1 at slot 1 (slot 2 taken by 6), Job 5 at slot 3, Jobs 4,3,2 cannot be scheduled due to slots taken. Total profit = 60+50+40=150.

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