Job Scheduling with Deadlines in DSA Typescript

Mental Model

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

Analogy: Imagine you have several tasks to do before certain times, but you can only do one task at a time. You pick the most valuable tasks that fit in your schedule without overlapping.

Jobs: [Job1: profit=20, deadline=2]
      [Job2: profit=15, deadline=2]
      [Job3: profit=10, deadline=1]
      [Job4: profit=5, deadline=3]
      [Job5: profit=1, deadline=3]

Schedule slots: 1 -> 2 -> 3 -> null
Each slot can hold one job before its deadline.

Dry Run Walkthrough

Input: Jobs: [(id=1, profit=20, deadline=2), (id=2, profit=15, deadline=2), (id=3, profit=10, deadline=1), (id=4, profit=5, deadline=3), (id=5, profit=1, deadline=3)]

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

Step 1: Sort jobs by profit descending

Jobs sorted: [1(20,2), 2(15,2), 3(10,1), 4(5,3), 5(1,3)]

Why: We want to try scheduling the most profitable jobs first to maximize profit.

Step 2: Schedule job 1 at latest free slot before deadline 2 (slot 2)

Schedule: slot1=null -> slot2=[1] -> slot3=null

Why: Job 1 deadline is 2, slot 2 is free, so assign job 1 there.

Step 3: Schedule job 2 at latest free slot before deadline 2 (slot 1)

Schedule: slot1=[2] -> slot2=[1] -> slot3=null

Why: Slot 2 is taken, try slot 1 which is free and before deadline.

Step 4: Schedule job 3 at latest free slot before deadline 1 (slot 1)

Schedule: slot1=[2] -> slot2=[1] -> slot3=null

Why: Slot 1 is taken by job 2, no free slot before deadline 1, so skip job 3.

Step 5: Schedule job 4 at latest free slot before deadline 3 (slot 3)

Schedule: slot1=[2] -> slot2=[1] -> slot3=[4]

Why: Slot 3 is free and before deadline 3, assign job 4.

Step 6: Schedule job 5 at latest free slot before deadline 3 (slots 3,2,1 all taken)

Schedule: slot1=[2] -> slot2=[1] -> slot3=[4]

Why: No free slot before deadline 3, skip job 5.

Result:

Final schedule: slot1=[2] -> slot2=[1] -> slot3=[4]
Total profit = 15 + 20 + 5 = 40

Annotated Code

DSA Typescript

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

function jobScheduling(jobs: Job[]): {schedule: (number | null)[], totalProfit: number} {
  // Sort jobs by profit descending
  jobs.sort((a, b) => b.profit - a.profit);

  // Find max deadline to size schedule
  const maxDeadline = jobs.length === 0 ? 0 : Math.max(...jobs.map(job => job.deadline));

  // Initialize schedule slots with null (empty)
  const schedule: (number | null)[] = new Array(maxDeadline).fill(null);

  let totalProfit = 0;

  for (const job of jobs) {
    // Try to schedule job at latest free slot before deadline
    for (let slot = Math.min(job.deadline, maxDeadline) - 1; slot >= 0; slot--) {
      if (schedule[slot] === null) {
        schedule[slot] = job.id; // assign job id to slot
        totalProfit += job.profit;
        break; // job scheduled, move to next job
      }
    }
  }

  return {schedule, totalProfit};
}

// Driver code
const jobs = [
  new Job(1, 20, 2),
  new Job(2, 15, 2),
  new Job(3, 10, 1),
  new Job(4, 5, 3),
  new Job(5, 1, 3),
];

const result = jobScheduling(jobs);
console.log("Schedule slots (index+1):", result.schedule);
console.log("Total profit:", result.totalProfit);

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 maximum deadline to know schedule size

const schedule: (number | null)[] = new Array(maxDeadline).fill(null);

Initialize schedule slots as empty

for (const job of jobs) {

Iterate over jobs in profit order

for (let slot = Math.min(job.deadline, maxDeadline) - 1; slot >= 0; slot--) {

Try to assign job to latest free slot before deadline

if (schedule[slot] === null) {

Check if slot is free

schedule[slot] = job.id; totalProfit += job.profit; break;

Assign job to slot, add profit, stop searching slots

Output

Schedule slots (index+1): [ 2, 1, 4 ]

Total profit: 40

Complexity Analysis

Time: O(n log n) because we sort n jobs by profit and then for each job try to find a slot in O(d) where d is max deadline, which is at most n.

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

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

Edge Cases

No jobs

Returns empty schedule and zero profit

DSA Typescript

const maxDeadline = jobs.length === 0 ? 0 : Math.max(...jobs.map(job => job.deadline));

All jobs have deadline 1

Only the highest profit job is scheduled in slot 1

DSA Typescript

for (let slot = Math.min(job.deadline, maxDeadline) - 1; slot >= 0; slot--)

Jobs with same profit and deadline

Schedules jobs in order they appear after sorting, filling earliest slots

DSA Typescript

if (schedule[slot] === null)

When to Use This Pattern

When you see tasks with deadlines and profits and need to maximize profit by scheduling without overlap, use the greedy job scheduling pattern by sorting jobs by profit and placing them in latest possible free slots.

Common Mistakes

Mistake: Scheduling jobs at earliest free slot instead of latest free slot before deadline.
Fix: Try slots from deadline backwards to find the latest free slot to maximize scheduling options.

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

Summary

Schedules jobs to maximize total profit without missing deadlines.

Use when you have tasks with deadlines and profits and want to maximize profit by scheduling non-overlapping tasks.

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 number of jobs without considering 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 goal

   The problem asks to schedule jobs so that total profit is maximized while respecting deadlines.

2. Step 2: Identify the objective

   Scheduling jobs before their deadlines to get maximum profit is the main goal.

3. Final Answer:

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

4. Quick Check:

   Goal = Maximize profit with deadlines [OK]

Hint: Focus on maximizing profit within deadlines [OK]

Common Mistakes:

• Ignoring deadlines and scheduling all jobs
• Trying to minimize jobs instead of maximizing profit
• Scheduling jobs in input order without sorting

2. Which of the following TypeScript code snippets correctly declares a job interface with id, deadline, and profit properties?

easy

A. type Job = { id: string; deadline: string; profit: string }

B. class Job { id; deadline; profit; }

C. interface Job { id: number; deadline: number; profit: number; }

D. interface Job { id; deadline; profit; }

Solution

1. Step 1: Check correct TypeScript interface syntax

   interface Job { id: number; deadline: number; profit: number; } correctly declares an interface with typed properties.

2. Step 2: Identify incorrect options

   type Job = { id: string; deadline: string; profit: string } uses strings instead of numbers, class Job { id; deadline; profit; } is a class without types, interface Job { id; deadline; profit; } misses types.

3. Final Answer:

   interface Job { id: number; deadline: number; profit: number; } -> Option C

4. Quick Check:

   Correct interface syntax = interface Job { id: number; deadline: number; profit: number; } [OK]

Hint: Use interface with typed properties for job data [OK]

Common Mistakes:

• Using class without types for data structure
• Omitting types in interface properties
• Using wrong types like string for numeric fields

3. What will be the output of the following TypeScript code that schedules jobs to maximize profit?

interface Job {
  id: string;
  deadline: number;
  profit: number;
}

const jobs: Job[] = [
  { 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 scheduleJobs(jobs: Job[]): string[] {
  jobs.sort((a, b) => b.profit - a.profit);
  const result: (string | null)[] = 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(id => id !== null) as string[];
}

console.log(scheduleJobs(jobs));

medium

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

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

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

D. ['a', 'b', 'c']

Solution

1. Step 1: Sort jobs by profit descending

   Sorted jobs: a(100), c(27), d(25), b(19), e(15).

2. Step 2: Schedule jobs in latest available slot before deadline

   Job 'a' scheduled at slot 1 (deadline 2), 'c' at slot 0 (deadline 2), 'd' cannot fit before deadline 1 (slot 0 taken), 'b' cannot fit, 'e' scheduled at slot 2 (deadline 3).

3. Final Answer:

   ['a', 'c', 'e'] -> Option B

4. Quick Check:

   Scheduled jobs = ['a', 'c', 'e'] [OK]

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

Common Mistakes:

• Scheduling jobs in input order without sorting
• Assigning earliest slot instead of latest
• Ignoring deadline constraints

4. Identify the bug in the following TypeScript function for job scheduling and select the correct fix.

function scheduleJobs(jobs: Job[]): string[] {
  jobs.sort((a, b) => a.profit - b.profit);
  const result: (string | null)[] = 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(id => id !== null) as string[];
}

medium

A. Sort jobs by profit descending instead of ascending

B. Initialize result array with zeros instead of null

C. Loop j from 0 to job.deadline - 1 instead of reverse

D. Remove the inner loop and assign jobs directly

Solution

1. Step 1: Analyze sorting order

   Jobs are sorted by profit ascending, which schedules low profit jobs first, reducing total profit.

2. Step 2: Correct sorting order

   Sorting by profit descending ensures high profit jobs are scheduled first for maximum profit.

3. Final Answer:

   Sort jobs by profit descending instead of ascending -> Option A

4. Quick Check:

   Profit descending sort fixes scheduling [OK]

Hint: Sort jobs by descending profit to fix scheduling [OK]

Common Mistakes:

• Sorting by ascending profit reduces total profit
• Changing loop direction incorrectly
• Using zero instead of null for empty slots

5. Given the following jobs with deadlines and profits, what is the maximum total profit achievable by scheduling jobs before their deadlines? Jobs: - Job1: deadline = 4, profit = 70 - Job2: deadline = 1, profit = 80 - Job3: deadline = 1, profit = 30 - Job4: deadline = 2, profit = 100 - Job5: deadline = 3, profit = 40 Select the correct maximum profit.

hard

A. 290

B. 210

C. 240

D. 230

Solution

1. Step 1: Sort jobs by profit descending

   Order: Job4(100), Job2(80), Job1(70), Job5(40), Job3(30).

2. Step 2: Schedule jobs in latest free slot before deadline

   Job4 at slot 1 (deadline 2), Job2 at slot 0 (deadline 1), Job1 at slot 3 (deadline 4), Job5 at slot 2 (deadline 3), Job3 cannot fit (slot 0 taken).

3. Step 3: Calculate total profit

   100 + 80 + 70 + 40 = 290, but slots are 0-based: slots 0,1,2,3 used. Actually, Job2 (deadline 1) at slot 0, Job4 (deadline 2) at slot 1, Job5 (deadline 3) at slot 2, Job1 (deadline 4) at slot 3. Total profit = 100 + 80 + 40 + 70 = 290.

4. Step 4: Re-check options

   Confirm scheduling: slots 0:Job2, 1:Job4, 2:Job5, 3:Job1. All fit, total 290.

5. Final Answer:

   290 -> Option A

6. Quick Check:

   Max profit = 290 [OK]

Hint: Schedule highest profit jobs first in latest free slot [OK]

Common Mistakes:

• Assuming all jobs fit without checking slots
• Adding profits of unscheduled jobs
• Misinterpreting deadlines as exact time slots