Job Scheduling with Deadlines in DSA Python - 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 deadline

Yes No↓

Assign job

↓

Repeat for next job

↓

End with scheduled jobs and total profit

Jobs are sorted by profit, then each is placed in the latest free slot before its deadline if possible, skipping if no slot is free.

Execution Sample

DSA Python

jobs = [(1, 2, 100), (2, 1, 19), (3, 2, 27), (4, 1, 25), (5, 3, 15)]
jobs.sort(key=lambda x: x[2], reverse=True)
schedule = [None]*3
for job in jobs:
    for slot in range(min(job[1], 3)-1, -1, -1):
        if schedule[slot] is None:
            schedule[slot] = job[0]
            break
print(schedule)

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

Execution Table

Step	Job (id, deadline, profit)	Slot checked	Slot free?	Action	Schedule state
1	(1, 2, 100)	1	Yes	Assign job 1 to slot 1	[None, 1, None]
2	(3, 2, 27)	1	No	Check slot 0	[None, 1, None]
2	(3, 2, 27)	0	Yes	Assign job 3 to slot 0	[3, 1, None]
3	(4, 1, 25)	0	No	No free slot, skip job 4	[3, 1, None]
4	(2, 1, 19)	0	No	No free slot, skip job 2	[3, 1, None]
5	(5, 3, 15)	2	Yes	Assign job 5 to slot 2	[3, 1, 5]

💡 All jobs processed or skipped; schedule filled or no free slots left.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
schedule	[None, None, None]	[None, 1, None]	[3, 1, None]	[3, 1, None]	[3, 1, None]	[3, 1, 5]	[3, 1, 5]

Key Moments - 2 Insights

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

Checking backwards ensures we assign the job to the latest possible free slot before its deadline, maximizing chances to schedule other jobs earlier (see execution_table steps 1 and 5).

Why are some jobs skipped even though they have profit?

If no free slot is available before the job's deadline, the job is skipped to avoid missing deadlines (see execution_table steps 3 and 4 where slots are occupied).

Visual Quiz - 3 Questions

Look at the execution_table, what is the schedule state after step 2?

A [None, 1, None]

B [3, 1, None]

C [2, None, None]

D [None, None, None]

💡 Hint

Check the 'Schedule state' column in row with Step 2.

Look at the execution_table, at which step is job 4 skipped because no free slot is found?

A Step 3

B Step 1

C Step 4

D Step 5

💡 Hint

Look for the row where job (4, 1, 25) is processed and no slot is free.

If the schedule had 4 slots instead of 3, what would happen to job 4?

A It would be assigned to slot 0

B It would be assigned to slot 3

C It would still be skipped

D It would replace job 2

💡 Hint

Even with 4 slots, job 4 has deadline 1, so it only checks slot 0, which is occupied by job 3 (see step 2).

Concept Snapshot

Job Scheduling with Deadlines:
- Sort jobs by profit descending
- For each job, assign to latest free slot before deadline
- Skip if no slot free
- Maximizes total profit
- Schedule represented as array of slots
- Output is scheduled job IDs per slot

Full Transcript

Job Scheduling with Deadlines means we have jobs each with a deadline and profit. We want to schedule jobs to maximize profit without missing deadlines. We first sort jobs by profit from highest to lowest. Then, for each job, we try to put it in the latest free slot before its deadline. If no slot is free, we skip that job. We keep track of which slots are filled. The final schedule shows which jobs are assigned to which slots. This method ensures maximum profit by prioritizing high-profit jobs and placing them as late as possible before their deadlines.

Practice

1. What is the main goal of the Job Scheduling with Deadlines problem?

easy

A. Schedule jobs in the order they arrive without considering deadlines

B. Maximize the total profit by scheduling jobs before their deadlines

C. Minimize the number of jobs scheduled

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.

2. Step 2: Identify the optimization criteria

   We want to maximize the total profit earned from scheduled jobs, not just the count.

3. Final Answer:

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

4. Quick Check:

   Goal = Maximize profit [OK]

Hint: Focus on maximizing profit within deadlines [OK]

Common Mistakes:

• Thinking it's about scheduling all jobs regardless of profit
• Confusing deadline with job duration
• Assuming jobs can be scheduled after deadlines

2. Which of the following is the correct Python syntax to sort a list of jobs by their profit in descending order? Assume each job is a tuple (job_id, deadline, profit).

easy

A. jobs.sort(key=lambda x: x[2], reverse=True)

B. jobs.sort(key=lambda x: x[1], reverse=True)

C. jobs.sort(reverse=True, key=lambda x: x[0])

D. jobs.sort(key=lambda x: x[2])

Solution

1. Step 1: Identify the sorting key

   Profit is at index 2 in each job tuple, so key=lambda x: x[2] is correct.

2. Step 2: Sort in descending order

   Use reverse=True to sort profits from highest to lowest.

3. Final Answer:

   jobs.sort(key=lambda x: x[2], reverse=True) -> Option A

4. Quick Check:

   Sort by profit descending = jobs.sort(key=lambda x: x[2], reverse=True) [OK]

Hint: Sort by profit descending using key and reverse=True [OK]

Common Mistakes:

• Sorting by deadline instead of profit
• Forgetting reverse=True for descending order
• Using wrong tuple index for profit

3. What is the output of the following code snippet?

jobs = [(1, 4, 20), (2, 1, 10), (3, 1, 40), (4, 1, 30)]
jobs.sort(key=lambda x: x[2], reverse=True)
slots = [False] * 4
result = [None] * 4
for job in jobs:
    for j in range(min(4, job[1]) - 1, -1, -1):
        if not slots[j]:
            slots[j] = True
            result[j] = job[0]
            break
print(result)

medium

A. [3, None, None, 1]

B. [4, 3, 1, None]

C. [1, 4, 3, None]

D. [None, 3, 4, 1]

Solution

1. Step 1: Sort jobs by profit descending

   Sorted jobs: (3,1,40), (4,1,30), (1,4,20), (2,1,10)

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

   Job 3: deadline 1, slot 0 free -> assign slot 0 = 3 Job 4: deadline 1, slot 0 taken, no earlier slot -> skip Job 1: deadline 4, slots 3 to 0 checked, slot 3 free -> assign slot 3 = 1 Job 2: deadline 1, slot 0 taken, no earlier slot -> skip

3. Final Answer:

   [3, None, None, 1] -> Option A

4. Quick Check:

   Result = [3, None, None, 1] [OK]

Hint: Assign jobs from highest profit to latest free slot before deadline [OK]

Common Mistakes:

• Assigning jobs to earliest slot instead of latest
• Not sorting jobs by profit first
• Confusing slot indices with deadlines

4. The following code attempts to schedule jobs with deadlines and maximize profit. What is the bug?

jobs = [(1, 2, 100), (2, 1, 19), (3, 2, 27), (4, 1, 25), (5, 3, 15)]
jobs.sort(key=lambda x: x[2])  # Sort by profit ascending
slots = [False] * 3
result = [None] * 3
for job in jobs:
    for j in range(min(3, job[1])):
        if not slots[j]:
            slots[j] = True
            result[j] = job[0]
            break
print(result)

medium

A. Result array is not initialized properly

B. Slots array size is too small

C. Inner loop should iterate backwards from deadline to 0

D. Jobs are sorted by profit ascending instead of descending

Solution

1. Step 1: Check sorting order

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

2. Step 2: Understand scheduling impact

   Scheduling low profit jobs first reduces total profit; sorting must be descending.

3. Final Answer:

   Jobs are sorted by profit ascending instead of descending -> Option D

4. Quick Check:

   Sort order must be descending for max profit [OK]

Hint: Sort jobs by profit descending to maximize profit [OK]

Common Mistakes:

• Sorting by ascending profit
• Iterating slots forward instead of backward (less critical here)
• Ignoring slot size mismatch

5. Given jobs [(1, 2, 100), (2, 1, 19), (3, 2, 27), (4, 1, 25), (5, 3, 15)], what is the maximum total profit achievable by scheduling jobs before their deadlines? Assume each job takes 1 unit time and only one job can be scheduled at a time.

hard

A. 115

B. 152

C. 142

D. 127

Solution

1. Step 1: Sort jobs by profit descending

   Sorted jobs: (1,2,100), (3,2,27), (4,1,25), (2,1,19), (5,3,15)

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

   Job 1: deadline 2, assign slot 2 (index 1) Job 3: deadline 2, assign slot 1 (index 0) Job 4: deadline 1, slot 0 taken, skip Job 2: deadline 1, slot 0 taken, skip Job 5: deadline 3, assign slot 3 (index 2)

3. Step 3: Calculate total profit

   Scheduled jobs: 1 (100), 3 (27), 5 (15) Total profit = 100 + 27 + 15 = 142

4. Final Answer:

   142 -> Option C

5. Quick Check:

   Total profit = 142 [OK]

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

Common Mistakes:

• Scheduling jobs without sorting by profit
• Assigning jobs to earliest slot instead of latest
• Counting jobs beyond deadline slots