Job Scheduling with Deadlines in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the Job class with id, deadline, and profit fields.

DSA Java

class Job {
    int id;
    int deadline;
    int [1];

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

Drag options to blanks, or click blank then click option'

Atime

Bweight

Cduration

Dprofit

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'time' or 'duration' instead of 'profit' for the profit field.

The Job class needs a 'profit' field to store the profit value for each job.

2fill in blank

medium

Complete the code to sort the jobs array by profit in descending order.

DSA Java

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

Drag options to blanks, or click blank then click option'

Aprofit

Bdeadline

Cid

Dlength

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting by deadline or id instead of profit.

We sort by 'profit' to schedule jobs with higher profit first.

3fill in blank

hard

Fix the error in the loop that tries to find a free slot for a job before its deadline.

DSA Java

for (int j = Math.min(maxDeadline, jobs[i].deadline) - 1; j >= 0; j--) {
    if (slot[j] == [1]) {
        result[j] = i;
        slot[j] = true;
        break;
    }
}

Drag options to blanks, or click blank then click option'

Afalse

Btrue

Cnull

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Checking if slot[j] is true instead of false.

We check if the slot is free by seeing if slot[j] is false (not taken).

4fill in blank

hard

Fill both blanks to initialize the slot array and result array for scheduling.

DSA Java

boolean[] slot = new boolean[[1]];
int[] result = new int[[2]];
for (int i = 0; i < [1]; i++) {
    slot[i] = false;
    result[i] = -1;
}

Drag options to blanks, or click blank then click option'

AmaxDeadline

Bjobs.length

CmaxProfit

DmaxDeadline + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using jobs.length or maxProfit for array sizes.

Both arrays should be sized by maxDeadline to cover all possible slots.

5fill in blank

hard

Fill all three blanks to print the scheduled jobs in order with their profits.

DSA Java

System.out.print("Scheduled jobs: ");
for (int i = 0; i < [1]; i++) {
    if (result[i] != -1) {
        System.out.print(jobs[result[i]].[2] + "(" + jobs[result[i]].[3] + ") ");
    }
}

Drag options to blanks, or click blank then click option'

AmaxDeadline

Bid

Cprofit

Djobs.length

Attempts:

3 left

💡 Hint

Common Mistakes

Looping over jobs.length instead of maxDeadline.

Printing wrong fields like deadline.

We loop up to maxDeadline and print job id and profit for scheduled jobs.

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