Job Scheduling with Deadlines in DSA Java - Time & Space Complexity

Time Complexity: Job Scheduling with Deadlines

O(n^2)

Understanding Time Complexity

We want to understand how the time needed to schedule jobs changes as we add more jobs.

How does the scheduling time grow when the number of jobs increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

// Scheduling jobs to maximize profit
void scheduleJobs(Job[] jobs) {
  Arrays.sort(jobs, (a, b) -> b.profit - a.profit);
  boolean[] slot = new boolean[jobs.length];
  for (Job job : jobs) {
    for (int j = Math.min(jobs.length, job.deadline) - 1; j >= 0; j--) {
      if (!slot[j]) { slot[j] = true; break; }
    }
  }
}
    

This code sorts jobs by profit and tries to schedule each job before its deadline in the latest free slot.

Identify Repeating Operations

Look for loops and repeated steps.

• Primary operation: The nested loops where for each job we check slots backward to find a free one.
• How many times: Outer loop runs once per job (n times), inner loop can run up to n times in worst case.

How Execution Grows With Input

As the number of jobs grows, the sorting takes more time, and checking slots for each job also takes longer.

Input Size (n)	Approx. Operations
10	About 100 (sorting + slot checks)
100	About 10,000 (sorting + slot checks)
1000	About 1,000,000 (sorting + slot checks)

Pattern observation: The time grows roughly with the square of the number of jobs.

Final Time Complexity

Time Complexity: O(n2)

This means if you double the number of jobs, the time to schedule them roughly quadruples.

Common Mistake

[X] Wrong: "Since we only loop through jobs once, the time is O(n)."

[OK] Correct: Each job may check many slots backward, causing a nested loop effect that increases time much more than just one pass.

Interview Connect

Understanding how nested loops affect time helps you explain your solution clearly and shows you can analyze efficiency well.

Self-Check

"What if we used a data structure to find free slots faster? How would the time complexity change?"

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