Job Scheduling with Deadlines in DSA Javascript

Mental Model

We want to schedule jobs so that we finish as many as possible before their deadlines, choosing the most profitable ones first.

Analogy: Imagine you have a list of tasks to do before certain times, and each task gives you some money. You pick tasks that pay the most and fit them into your schedule without overlapping.

Jobs: [Job1: profit=20, deadline=2]
      [Job2: profit=15, deadline=2]
      [Job3: profit=10, deadline=1]
      Schedule slots: [ _ ] [ _ ] (time 1 and 2)
      Goal: Fill slots with jobs to maximize profit.

Dry Run Walkthrough

Input: Jobs: [{id: 'A', profit: 20, deadline: 2}, {id: 'B', profit: 15, deadline: 2}, {id: 'C', profit: 10, deadline: 1}]

Goal: Schedule jobs to maximize total profit without missing deadlines.

Step 1: Sort jobs by profit descending

Jobs sorted: A(20,2) -> B(15,2) -> C(10,1)

Why: We want to consider the most profitable jobs first to maximize total profit.

Step 2: Schedule job A at latest available slot before deadline 2

Schedule: [ _ ] -> [A] (time slots 1 and 2)

Why: Job A has deadline 2, so we try to put it at time 2 to leave earlier slots free.

Step 3: Schedule job B at latest available slot before deadline 2

Schedule: [B] -> [A]

Why: Time slot 2 is taken by A, so B goes to slot 1 which is free and before deadline 2.

Step 4: Try to schedule job C before deadline 1

Schedule: [B] -> [A]

Why: Slot 1 is taken by B, so C cannot be scheduled.

Result:

Schedule: B -> A
Total profit: 35

Annotated Code

DSA Javascript

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

function jobScheduling(jobs) {
  // Sort jobs by profit descending
  jobs.sort((a, b) => b.profit - a.profit);

  const maxDeadline = Math.max(...jobs.map(job => job.deadline));
  const schedule = new Array(maxDeadline).fill(null);

  for (const job of jobs) {
    // Try to schedule job at latest slot before deadline
    for (let slot = job.deadline - 1; slot >= 0; slot--) {
      if (schedule[slot] === null) {
        schedule[slot] = job;
        break; // job scheduled
      }
    }
  }

  // Prepare output
  const scheduledJobs = schedule.filter(j => j !== null).map(j => j.id);
  const totalProfit = schedule.filter(j => j !== null).reduce((sum, j) => sum + j.profit, 0);

  console.log('Scheduled jobs:', scheduledJobs.join(' -> '));
  console.log('Total profit:', totalProfit);
}

// Driver code
const jobs = [
  new Job('A', 20, 2),
  new Job('B', 15, 2),
  new Job('C', 10, 1)
];
jobScheduling(jobs);

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

Sort jobs by profit descending to prioritize high profit jobs

const maxDeadline = Math.max(...jobs.map(job => job.deadline));

Find the maximum deadline to size the schedule array

const schedule = new Array(maxDeadline).fill(null);

Initialize schedule slots as empty

for (const job of jobs) {

Iterate over jobs in order of profit

for (let slot = job.deadline - 1; slot >= 0; slot--) {

Try to place job in latest available slot before deadline

if (schedule[slot] === null) { schedule[slot] = job; break; }

Assign job to slot if free and stop searching

const scheduledJobs = schedule.filter(j => j !== null).map(j => j.id);

Collect scheduled job ids for output

const totalProfit = schedule.filter(j => j !== null).reduce((sum, j) => sum + j.profit, 0);

Sum profits of scheduled jobs

Output

Scheduled jobs: B -> A

Total profit: 35

Complexity Analysis

Time: O(n log n) because we sort the jobs by profit and then try to schedule each job in at most its deadline slots

Space: O(n) for the schedule array and job list

vs Alternative: Naive approach tries all permutations which is factorial time; this greedy approach is efficient and practical

Edge Cases

No jobs

Output is empty schedule and zero profit

DSA Javascript

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

All jobs have deadline 1

Only the highest profit job is scheduled

DSA Javascript

for (let slot = job.deadline - 1; slot >= 0; slot--) {

Jobs with same profit and deadline

Jobs are scheduled in order they appear after sorting, filling earliest slots

DSA Javascript

if (schedule[slot] === null) { schedule[slot] = job; break; }

When to Use This Pattern

When you see tasks with deadlines and profits and need to maximize profit by scheduling, use the greedy job scheduling pattern to pick highest profit jobs first and assign them to latest free slots before their deadlines.

Common Mistakes

Mistake: Scheduling jobs at earliest slot instead of latest slot before deadline
Fix: Try slots from deadline backwards to maximize slot availability for other jobs

Mistake: Not sorting jobs by profit descending
Fix: Sort jobs by profit descending before scheduling to prioritize high profit jobs

Summary

Schedules jobs to maximize total profit without missing deadlines.

Use when you have jobs with deadlines and profits and want to maximize profit by scheduling.

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

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