Job Scheduling with Deadlines in DSA Typescript - Execution Trace

Concept Flow - Job Scheduling with Deadlines

Start with list of jobs

↓

Sort jobs by profit descending

↓

Initialize schedule slots as empty

↓

For each job in sorted list

↓

Find latest free slot before job deadline

↓

If slot found, assign job to slot

↓

Repeat for all jobs

↓

Output scheduled jobs and total profit

Sort jobs by profit, then assign each to the latest free slot before its deadline to maximize total profit.

Execution Sample

DSA Typescript

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

// Schedule jobs to maximize profit within deadlines

This code schedules jobs by sorting them by profit and placing each in the latest available slot before its deadline.

Execution Table

Step	Current Job	Sorted Jobs	Slot Checked	Slot Assigned	Schedule State	Total Profit
1	Start	[J1(2,100), J2(1,19), J3(2,27), J4(1,25), J5(3,15)]	-	-	[null, null, null]	0
2	Pick J1(2,100)	[J1(2,100), J3(2,27), J4(1,25), J2(1,19), J5(3,15)]	Slot 2	Slot 2	[null, J1, null]	100
3	Pick J3(2,27)	[J3(2,27), J4(1,25), J2(1,19), J5(3,15)]	Slot 2 (occupied), Slot 1	Slot 1	[J3, J1, null]	127
4	Pick J4(1,25)	[J4(1,25), J2(1,19), J5(3,15)]	Slot 1 (occupied)	No slot	[J3, J1, null]	127
5	Pick J2(1,19)	[J2(1,19), J5(3,15)]	Slot 1 (occupied)	No slot	[J3, J1, null]	127
6	Pick J5(3,15)	[J5(3,15)]	Slot 3	Slot 3	[J3, J1, J5]	142
7	End	-	-	-	[J3, J1, J5]	142

💡 All jobs processed or no free slots available for remaining jobs.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
schedule	[null, null, null]	[null, J1, null]	[J3, J1, null]	[J3, J1, null]	[J3, J1, null]	[J3, J1, J5]	[J3, J1, J5]
totalProfit	0	100	127	127	127	142	142

Key Moments - 2 Insights

Why do we check slots from the job's deadline backwards?

Checking slots backward ensures we place the job as late as possible before its deadline, leaving earlier slots free for other jobs, as shown in steps 3 and 6.

Why can't some jobs be scheduled even if there are empty slots?

If all slots before a job's deadline are occupied, the job cannot be scheduled, like in steps 4 and 5 where slot 1 is already taken.

Visual Quiz - 3 Questions

Look at the execution table at Step 3. Which slot was finally assigned to job J3?

A Slot 3

B Slot 2

C Slot 1

D No slot assigned

💡 Hint

Check the 'Slot Assigned' column at Step 3 in the execution table.

At which step does the total profit first reach 127?

A Step 3

B Step 4

C Step 2

D Step 6

💡 Hint

Look at the 'Total Profit' column in the execution table for the value 127.

If job J5 had a deadline of 1 instead of 3, what would happen to the schedule at Step 6?

A J5 would be assigned to Slot 1

B J5 would not be assigned any slot

C J5 would be assigned to Slot 3

D J5 would replace J3 in Slot 1

💡 Hint

Refer to how slots are assigned before deadlines in the execution table and variable tracker.

Concept Snapshot

Job Scheduling with Deadlines:
- Sort jobs by profit descending.
- For each job, find latest free slot before deadline.
- Assign job to that slot if available.
- Maximize total profit by greedy placement.
- Slots represent time units; no overlaps allowed.

Full Transcript

Job Scheduling with Deadlines is a method to maximize profit by scheduling jobs within their deadlines. We start with a list of jobs, each having a deadline and profit. First, we sort jobs by profit from highest to lowest. Then, for each job, we try to place it in the latest available slot before its deadline. If the slot is free, we assign the job there; if not, we check earlier slots. This process continues until all jobs are checked. The schedule shows which jobs fit in which slots, and the total profit sums the profits of scheduled jobs. Some jobs may not fit if all slots before their deadlines are taken. This greedy approach ensures maximum profit by prioritizing high-profit jobs and placing them as late as possible to leave room for others.

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