Job Scheduling with Deadlines in DSA Javascript - 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 grows as the number of jobs increases.

How does the scheduling process scale when we have more jobs with deadlines?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function scheduleJobs(jobs) {
  jobs.sort((a, b) => b.profit - a.profit);
  const result = [];
  const slot = Array(jobs.length).fill(false);
  for (let i = 0; i < jobs.length; i++) {
    for (let j = Math.min(jobs[i].deadline - 1, jobs.length - 1); j >= 0; j--) {
      if (!slot[j]) {
        slot[j] = true;
        result[j] = jobs[i];
        break;
      }
    }
  }
  return result;
}
  

This code schedules jobs to maximize profit by placing each job in the latest available slot before its deadline.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops where the outer loop goes through each job and the inner loop searches for a free slot before the job's deadline.
• 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 the nested loops check slots for each job.

Input Size (n)	Approx. Operations
10	About 100 operations
100	About 10,000 operations
1000	About 1,000,000 operations

Pattern observation: The operations grow roughly by the square of the input size.

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: The inner loop that finds a free slot can run many times for each job, making the total work much larger than just one pass.

Interview Connect

Understanding how nested loops affect time helps you explain your approach clearly and shows you can analyze efficiency in real problems.

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 total profit by scheduling jobs before their deadlines

B. Minimize the number of jobs scheduled

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

D. Maximize the number of jobs scheduled regardless of profit

Solution

1. Step 1: Understand the problem goal

   The problem aims to schedule jobs so that each job finishes before its deadline and the total profit is maximized.

2. Step 2: Identify the objective

   Maximizing total profit means choosing jobs carefully, not just scheduling all or in order.

3. Final Answer:

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

4. Quick Check:

   Goal = Maximize profit before deadlines [OK]

Hint: Focus on profit and deadlines to maximize earnings [OK]

Common Mistakes:

• Ignoring deadlines and scheduling all jobs
• Trying to schedule jobs in input order
• Maximizing number of jobs instead of profit

2. Which of the following is the correct way to sort jobs by profit in descending order in JavaScript?

easy

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

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

C. jobs.sort((a, b) => a.deadline - b.deadline);

D. jobs.sort((a, b) => b.deadline - a.deadline);

Solution

1. Step 1: Understand sorting by profit descending

   To sort descending, subtract b.profit - a.profit so higher profits come first.

2. Step 2: Check the options

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

3. Final Answer:

   jobs.sort((a, b) => b.profit - a.profit); -> Option B

4. Quick Check:

   Descending profit sort = b.profit - a.profit [OK]

Hint: Use b - a for descending numeric sort in JavaScript [OK]

Common Mistakes:

• Using a.profit - b.profit which sorts ascending
• Sorting by deadline instead of profit
• Confusing ascending and descending order

3. Given the jobs array:

const jobs = [
  {id: 'a', deadline: 2, profit: 100},
  {id: 'b', deadline: 1, profit: 19},
  {id: 'c', deadline: 2, profit: 27},
  {id: 'd', deadline: 1, profit: 25},
  {id: 'e', deadline: 3, profit: 15}
];

After scheduling jobs to maximize profit with deadlines, which jobs are selected (in order of scheduling)?

medium

A. ['b', 'd', 'e']

B. ['a', 'c', 'e']

C. ['a', 'd']

D. ['a', 'd', 'e']

Solution

1. Step 1: Sort jobs by profit descending

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

2. Step 2: Schedule jobs greedily before deadlines

   Schedule 'a' at latest slot <=2 (slot 2), 'c' at latest <=2 (slot 1 since 2 taken), skip 'b' (slot 1 taken), 'd' at slot 1 (since 'c' was assigned slot 1, 'd' cannot be assigned), 'e' at latest <=3 (slot 3). Correct scheduling is 'a' at slot 2, 'd' at slot 1, 'e' at slot 3. Order: ['a', 'd', 'e']

3. Final Answer:

   ['a', 'd', 'e'] -> Option D

4. Quick Check:

   Max profit jobs scheduled = ['a', 'd', 'e'] [OK]

Hint: Sort by profit, assign latest free slot before deadline [OK]

Common Mistakes:

• Scheduling jobs only by deadline order
• Ignoring profit and picking lower profit jobs
• Not checking slot availability before deadline

4. Consider this code snippet for job scheduling:

jobs.sort((a, b) => b.profit - a.profit);
const result = [];
const slot = Array(jobs.length).fill(false);
for (let job of jobs) {
  for (let j = 0; j <= job.deadline; j++) {
    if (!slot[j]) {
      slot[j] = true;
      result.push(job.id);
      break;
    }
  }
}
console.log(result);

What is the main bug in this code?

medium

A. The jobs array is not sorted by deadline

B. The slot array should be initialized with true, not false

C. The inner loop should run from job.deadline down to 1, not 0 up to deadline

D. The result array should store job profits, not ids

Solution

1. Step 1: Analyze slot assignment loop

   The inner loop checks slots from 0 up to deadline, but slots should be checked from deadline down to 1 to assign latest free slot.

2. Step 2: Understand correct slot checking order

   Checking from deadline down ensures jobs are scheduled as late as possible before deadline, maximizing slot usage.

3. Final Answer:

   The inner loop should run from job.deadline down to 1, not 0 up to deadline -> Option C

4. Quick Check:

   Check slots backward from deadline [OK]

Hint: Check slots backward from deadline to assign latest free slot [OK]

Common Mistakes:

• Checking slots forward from 0 wastes early slots
• Initializing slot array incorrectly
• Confusing sorting criteria

5. You have jobs with deadlines and profits:

const jobs = [
  {id: 'j1', deadline: 4, profit: 70},
  {id: 'j2', deadline: 1, profit: 80},
  {id: 'j3', deadline: 1, profit: 30},
  {id: 'j4', deadline: 2, profit: 100},
  {id: 'j5', deadline: 3, profit: 40}
];

Using job scheduling with deadlines, what is the maximum total profit and which jobs are scheduled?

hard

A. Total profit 290; jobs scheduled: ['j4', 'j2', 'j1', 'j5']

B. Total profit 220; jobs scheduled: ['j2', 'j4', 'j1']

C. Total profit 240; jobs scheduled: ['j4', 'j2', 'j5', 'j3']

D. Total profit 210; jobs scheduled: ['j2', 'j4', 'j5']

Solution

1. Step 1: Sort jobs by profit descending

   Sorted: j4(100,2), j2(80,1), j1(70,4), j5(40,3), j3(30,1)

2. Step 2: Schedule jobs greedily before deadlines

   Assign j4 at slot 2, j2 at slot 1, j1 at slot 4, j5 at slot 3. j3 cannot fit. Total profit: 100+80+70+40=290. Scheduled: ['j4', 'j2', 'j1', 'j5']

3. Final Answer:

   Total profit 290; jobs scheduled: ['j4', 'j2', 'j1', 'j5'] -> Option A

4. Quick Check:

   Max profit = 290 with jobs j4,j2,j1,j5 [OK]

Hint: Sort by profit, assign latest free slot before deadline, sum profits [OK]

Common Mistakes:

• Not assigning jobs to latest possible slot
• Miscounting total profit
• Ignoring job deadlines when scheduling