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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Job Scheduling with Deadlines Algorithm

What is the output of the following job scheduling code that schedules jobs to maximize profit within their deadlines?

DSA Javascript

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}
];

function jobScheduling(jobs) {
  jobs.sort((a, b) => b.profit - a.profit);
  const result = Array(jobs.length).fill(null);
  for (const job of jobs) {
    for (let j = Math.min(jobs.length, job.deadline) - 1; j >= 0; j--) {
      if (result[j] === null) {
        result[j] = job.id;
        break;
      }
    }
  }
  return result.filter(x => x !== null).join(' -> ') + ' -> null';
}

console.log(jobScheduling(jobs));

A a -> d -> e -> null

B a -> b -> e -> null

C c -> a -> e -> null

D a -> c -> d -> null

💡 Hint

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

The algorithm sorts jobs by profit descending: a(100), c(27), d(25), b(19), e(15). It tries to schedule each job in the latest free slot before its deadline. 'a' goes to slot 1, 'c' to slot 0 (deadline 2 means slot 1 or 0), 'e' to slot 2. 'd' and 'b' cannot be scheduled because slots are taken. So output is 'c -> a -> e -> null'.

🧠 Conceptual

intermediate

Maximum Number of Jobs Scheduled

Given 4 jobs with deadlines and profits, what is the maximum number of jobs that can be scheduled without missing deadlines?

A 3

B 4

C 2

D 1

💡 Hint

Consider the maximum deadline and available slots.

The maximum number of jobs scheduled equals the number of available time slots before the maximum deadline. If maximum deadline is 3, at most 3 jobs can be scheduled.

🔧 Debug

advanced

Identify the Bug in Job Scheduling Code

What error does the following job scheduling code produce when run?

DSA Javascript

function scheduleJobs(jobs) {
  jobs.sort((a, b) => a.profit - b.profit);
  const result = Array(jobs.length).fill(null);
  for (const job of jobs) {
    for (let j = job.deadline - 1; j >= 0; j--) {
      if (result[j] === null) {
        result[j] = job.id;
        break;
      }
    }
  }
  return result.filter(x => x !== null).join(' -> ') + ' -> null';
}

const jobs = [
  {id: 'x', deadline: 2, profit: 50},
  {id: 'y', deadline: 1, profit: 60}
];

console.log(scheduleJobs(jobs));

A Output: y -> x -> null

B Output: x -> y -> null

C Output: y -> null

D Output: x -> null

💡 Hint

Check the sorting order and how jobs are assigned to slots.

The code sorts jobs by ascending profit, so job 'x' (50) is scheduled before 'y' (60). 'x' is assigned to slot 1 (deadline 2), 'y' tries slot 0 (deadline 1) and slot 0 is free, so 'y' is assigned there. The output is 'y -> x -> null'. The bug is the ascending sort (should be descending to prioritize higher profit).

📝 Syntax

advanced

Syntax Error in Job Scheduling Code

Which option contains the syntax error when trying to implement job scheduling with deadlines?

A return result.filter(x => x !== null).join(' -> ') + ' -> null';

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

C const result = new Array(jobs.length).fill(null);

D for (let j = job.deadline; j >= 0; j--) { if (result[j] === null) { result[j] = job.id; break; } }

💡 Hint

Check array indexing and loop boundaries carefully.

Option D uses 'for (let j = job.deadline; j >= 0; j--)' which tries to access result[j] where j can be equal to job.deadline, which is out of array bounds (0-based index). The correct loop should start from job.deadline - 1.

🚀 Application

expert

Maximum Profit from Job Scheduling

Given the jobs below, what is the maximum total profit achievable by scheduling jobs within their deadlines?

DSA Javascript

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},
  {id: 'j6', deadline: 2, profit: 20}
];

A 260

B 290

C 270

D 310

💡 Hint

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

Sorted by profit descending: j4(100), j2(80), j1(70), j5(40), j3(30), j6(20). Schedule j4 at slot 1 (deadline 2), j2 at slot 0 (deadline 1), j1 at slot 3 (deadline 4), j5 at slot 2 (deadline 3). j3 and j6 cannot be scheduled because slots are full. Total profit = 100 + 80 + 70 + 40 = 290. But we must check if j1 can be scheduled at slot 3 (index 3), which is valid. So total profit is 290. Option B (310) is incorrect, correct is 290 (Option B).

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