Job Scheduling with Deadlines in DSA Python

Mental Model

We want to schedule jobs to get the most profit by finishing them before their deadlines. We pick jobs that pay the most first and fit them in available time slots.

Analogy: Imagine you have several tasks to do before certain times, and each task gives you money. You want to do the most valuable tasks first but only if you can finish them on time, like fitting appointments in a calendar.

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]

Time slots: 1 -> 2 -> 3 -> null
Slots are empty initially: _ -> _ -> _ -> null

Dry Run Walkthrough

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

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

Step 1: Sort jobs by profit descending

Jobs sorted: [20@2, 15@2, 10@1, 5@3, 1@3]

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

Step 2: Schedule job with profit 20 and deadline 2 in slot 2

Slots: _ -> [20] -> _ -> null

Why: Try to place job as late as possible before its deadline to leave earlier slots free.

Step 3: Schedule job with profit 15 and deadline 2 in slot 1 (slot 2 taken)

Slots: [15] -> [20] -> _ -> null

Why: Slot 2 is taken, so place job in the next available earlier slot.

Step 4: Schedule job with profit 10 and deadline 1 in slot 1 (taken), cannot schedule

Slots: [15] -> [20] -> _ -> null

Why: No free slot before deadline 1, so skip this job.

Step 5: Schedule job with profit 5 and deadline 3 in slot 3

Slots: [15] -> [20] -> [5] -> null

Why: Slot 3 is free and before deadline, so schedule job here.

Step 6: Schedule job with profit 1 and deadline 3 in slot 3 (taken), slot 2 (taken), slot 1 (taken), cannot schedule

Slots: [15] -> [20] -> [5] -> null

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

Result:

Slots: [15] -> [20] -> [5] -> null
Total profit = 15 + 20 + 5 = 40

Annotated Code

DSA Python

class Job:
    def __init__(self, profit, deadline):
        self.profit = profit
        self.deadline = deadline

def job_scheduling(jobs):
    if not jobs:
        return 'null', 0
    # Sort jobs by profit descending
    jobs.sort(key=lambda x: x.profit, reverse=True)

    max_deadline = max(job.deadline for job in jobs)
    slots = [None] * max_deadline  # None means free slot

    for job in jobs:
        # Try to schedule job in latest possible slot before deadline
        for slot in range(min(max_deadline, job.deadline) - 1, -1, -1):
            if slots[slot] is None:
                slots[slot] = job
                break

    # Prepare output string
    result = []
    total_profit = 0
    for slot in slots:
        if slot is None:
            result.append('_')
        else:
            result.append(str(slot.profit))
            total_profit += slot.profit
    schedule_str = ' -> '.join(result) + ' -> null'
    return schedule_str, total_profit

# Driver code
jobs = [Job(20, 2), Job(15, 2), Job(10, 1), Job(5, 3), Job(1, 3)]
schedule_str, total_profit = job_scheduling(jobs)
print(schedule_str)
print(f"Total profit = {total_profit}")

jobs.sort(key=lambda x: x.profit, reverse=True)

Sort jobs by profit descending to prioritize high profit jobs

max_deadline = max(job.deadline for job in jobs)

Find the maximum deadline to know number of slots

slots = [None] * max_deadline

Initialize all slots as free

for job in jobs:

Try scheduling each job in order of profit

for slot in range(min(max_deadline, job.deadline) - 1, -1, -1):

Check slots from job's deadline backwards to find free slot

if slots[slot] is None:

If slot is free, assign job here

Output

15 -> 20 -> 5 -> null

Total profit = 40

Complexity Analysis

Time: O(n log n) because we sort the jobs by profit and then for each job we try to find a slot which can take O(n) in worst case

Space: O(n) for the slots array to keep track of scheduled jobs

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

Edge Cases

No jobs

Returns empty schedule with zero profit

DSA Python

if not jobs: return 'null', 0

All jobs have deadline 1

Only the highest profit job is scheduled

DSA Python

for slot in range(min(max_deadline, job.deadline) - 1, -1, -1):

Multiple jobs with same deadline and profit

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

DSA Python

if slots[slot] is None:

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 assign jobs starting from highest profit to available slots before deadlines.

Common Mistakes

Mistake: Scheduling jobs in order of deadlines instead of profit
Fix: Sort jobs by profit descending to prioritize high profit jobs first

Mistake: Assigning jobs to earliest slot instead of latest slot before deadline
Fix: Try to assign jobs to the latest possible free slot before their deadline to leave room for other jobs

Summary

Schedules jobs to maximize total profit by fitting them before deadlines.

Use when you have tasks with deadlines and profits and want the best profit schedule.

Sort jobs by profit 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. 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