Job Scheduling with Deadlines in DSA Javascript - Execution Trace

Concept Flow - Job Scheduling with Deadlines

Start: List of Jobs

↓

Sort Jobs by Profit Desc

↓

Initialize Schedule Array

↓

For each Job in Sorted List

↓

Find Latest Free Slot Before Deadline

↓

If Slot Found, Assign Job

↓

Repeat for All Jobs

↓

Output Scheduled Jobs and Total Profit

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

Execution Sample

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

Defines a list of jobs with deadlines and profits to schedule.

Execution Table

Step	Action	Job Considered	Slot Checked	Slot Assigned	Schedule State	Total Profit
1	Sort jobs by profit descending	-	-	-	[_,_,_]	0
2	Consider job 'a'	a (deadline=2, profit=100)	Slot 2 free?	Yes	[_, a, _]	100
3	Consider job 'c'	c (deadline=2, profit=27)	Slot 2 free?	No	[_, a, _]	100
			Slot 1 free?	Yes	[c, a, _]	127
4	Consider job 'd'	d (deadline=1, profit=25)	Slot 1 free?	No	[c, a, _]	127
5	Consider job 'b'	b (deadline=1, profit=19)	Slot 1 free?	No	[c, a, _]	127
6	Consider job 'e'	e (deadline=3, profit=15)	Slot 3 free?	Yes	[c, a, e]	142
7	All jobs considered	-	-	-	[c, a, e]	142

💡 All jobs checked; schedule filled with maximum profit jobs.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
jobs	[a,b,c,d,e]	[a,c,d,b,e]	[a,c,d,b,e]	[a,c,d,b,e]	[a,c,d,b,e]	[a,c,d,b,e]	[a,c,d,b,e]	[a,c,d,b,e]
schedule	[_,_,_]	[_,_,_]	[_,a,_]	[c,a,_]	[c,a,_]	[c,a,_]	[c,a,e]	[c,a,e]
totalProfit	0	0	100	127	127	127	142	142

Key Moments - 3 Insights

Why do we check the latest free slot before the job's deadline instead of the earliest?

Checking the latest free slot (see Step 3 and 6 in execution_table) allows earlier slots to remain free for other jobs with earlier deadlines, maximizing total profit.

Why is job 'c' assigned to slot 1 instead of slot 2 which is taken after 'a' is assigned?

Slot 2 is already taken by 'a' (Step 3), so we check slot 1 which is free and before 'c's deadline, so 'c' is assigned there (Step 3).

Why are jobs 'd' and 'b' not scheduled even though they have deadlines?

Slots before their deadlines are already occupied by higher profit jobs (Step 4 and 5), so they cannot be assigned without reducing total profit.

Visual Quiz - 3 Questions

Look at the execution_table at Step 2. Which slot is job 'a' assigned to?

A Slot 2

B Slot 3

C Slot 1

D No slot assigned

💡 Hint

Check the 'Slot Assigned' and 'Schedule State' columns at Step 2 in execution_table.

At which step does the total profit first reach 127?

A Step 2

B Step 3

C Step 4

D Step 6

💡 Hint

Look at the 'Total Profit' column in execution_table and find when it changes to 127.

If job 'e' had a deadline of 1 instead of 3, what would happen to the schedule?

A Job 'e' would be assigned to slot 2

B Job 'e' would be assigned to slot 1

C Job 'e' would not be assigned

D Job 'e' would replace job 'a'

💡 Hint

Refer to variable_tracker and execution_table steps where slot 1 is already occupied.

Concept Snapshot

Job Scheduling with Deadlines:
- Sort jobs by profit descending.
- For each job, assign it to the latest free slot before its deadline.
- If no slot free, skip job.
- Maximizes total profit by scheduling high-profit jobs first.
- Schedule array tracks assigned jobs by slot.

Full Transcript

Job Scheduling with Deadlines is about choosing jobs to maximize profit without missing deadlines. We start with a list of jobs, each with a deadline and profit. First, we sort jobs by profit from highest to lowest. Then, for each job, we try to assign it to the latest free time slot before its deadline. If that slot is taken, we check earlier slots until we find a free one or none are free. We keep track of assigned jobs and total profit. Jobs that cannot fit are skipped. This way, we get the best profit schedule. The execution table shows each step: sorting, checking slots, assigning jobs, and updating profit. The variable tracker shows how jobs, schedule, and profit change over time. Key moments explain why we pick latest slots and why some jobs are skipped. The quiz tests understanding of slot assignment and profit calculation. This method ensures maximum profit by smartly scheduling jobs within deadlines.

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