Job Scheduling with Deadlines - Common Greedy Patterns | OneNoughtOne

0/361

Data Structures & AlgorithmsGreedy Algorithms

Common Greedy Patterns

LevelAdvanced

Duration90 mins

TopicGreedy Algorithms

1 / 4

Job Scheduling with Deadlines

The Scheduling Dilemma

Imagine you're a freelance consultant with multiple lucrative projects on your desk. Each project has a deadline and pays a specific amount upon completion. Here's the catch: each project takes exactly one day to complete, and you can only work on one project per day. If you miss a project's deadline, you get nothing—the client walks away.

This isn't just an abstract puzzle. It's the Job Scheduling with Deadlines Problem, one of the most elegant and instructive greedy patterns in algorithm design. The problem crystallizes a fundamental tension in resource allocation: how do you maximize total value when you can't do everything?

What You Will Learn

By the end of this page, you will understand the job scheduling problem deeply—its formal definition, the greedy strategy that solves it optimally, the slot allocation technique, correctness proof, time complexity analysis, and practical variations. You'll gain the ability to recognize this pattern in disguise across numerous scheduling and resource allocation problems.

Problem Formalization

Before diving into solutions, we must precisely define the problem. Imprecise understanding leads to faulty algorithms.

Input:

A set of n jobs: J = {J₁, J₂, ..., Jₙ}
Each job Jᵢ has:
- A profit pᵢ (earned only if completed on or before deadline)
- A deadline dᵢ (integer representing the latest day by which the job must be completed)
All jobs require exactly one time unit (one day) to complete
Only one job can be processed at a time

Output:

A subset S ⊆ J of jobs to schedule
A feasible schedule assigning each selected job to a unique time slot
Such that each job in S is completed on or before its deadline

Objective:

Maximize the total profit: Σ pᵢ for all Jᵢ ∈ S

Feasibility Constraint

A schedule is feasible if and only if every scheduled job completes by its deadline. If job Jᵢ has deadline dᵢ = 3, it must be assigned to time slot 1, 2, or 3—not slot 4 or later. The challenge is that multiple jobs might compete for the same slots.

Example Instance:

Consider 5 jobs with the following specifications:

Job Scheduling Instance
Job	Profit	Deadline
J₁	100	2
J₂	19	1
J₃	27	2
J₄	25	1
J₅	15	3

Observations from this instance:

Jobs J₂ and J₄ both have deadline 1—only one can be scheduled in slot 1
Jobs J₁ and J₃ have deadline 2—they can use slots 1 or 2
Job J₅ has the most flexibility with deadline 3
Maximum possible time slots needed: max(all deadlines) = 3
We can schedule at most 3 jobs (one per slot)

The greedy insight: We should prioritize high-profit jobs and try to schedule them as late as possible within their deadlines, leaving earlier slots for jobs with tighter deadlines.

The Greedy Strategy: Profit-First Selection

The greedy approach for job scheduling is beautifully intuitive: consider jobs in decreasing order of profit, and schedule each job if possible.

But what does "if possible" mean? A job can be scheduled if there exists at least one free time slot on or before its deadline. The key insight is which slot to use: we should assign the job to the latest available slot within its deadline window.

Why schedule late?

Scheduling a job as late as possible preserves earlier slots for jobs that might need them more urgently. A job with deadline 3 scheduled in slot 1 wastes flexibility—if another high-profit job with deadline 1 arrives later in our sorted order, we've already claimed its only viable slot.

The "Latest Slot First" Principle

When scheduling a job with deadline d, always use the latest available slot in [1, d]. This maximizes scheduling flexibility for subsequent jobs. This principle is sometimes called the "leave room" heuristic—don't consume resources you might not need.

The Algorithm:

JOB-SCHEDULING-WITH-DEADLINES(jobs):
    1. Sort jobs by profit in decreasing order
    2. Let dmax = maximum deadline among all jobs
    3. Initialize slots[1..dmax] = [free, free, ..., free]
    4. Initialize scheduled = empty list
    5. Initialize totalProfit = 0
    
    6. FOR each job j in sorted order:
    7.     FOR slot = j.deadline DOWN TO 1:
    8.         IF slots[slot] == free:
    9.             slots[slot] = j
    10.            scheduled.append(j)
    11.            totalProfit += j.profit
    12.            BREAK (move to next job)
    13.    // If no slot found, job j is not scheduled
    
    14. RETURN (scheduled, totalProfit)

Trace through our example:

Sorted by profit: J₁(100), J₃(27), J₄(25), J₂(19), J₅(15)

Step	Job	Profit	Deadline	Check Slots	Action	Slots State
1	J₁	100	2	slot 2? free	Schedule J₁ in slot 2	[_, J₁, _]
2	J₃	27	2	slot 2? taken, slot 1? free	Schedule J₃ in slot 1	[J₃, J₁, _]
3	J₄	25	1	slot 1? taken	Cannot schedule	[J₃, J₁, _]
4	J₂	19	1	slot 1? taken	Cannot schedule	[J₃, J₁, _]
5	J₅	15	3	slot 3? free	Schedule J₅ in slot 3	[J₃, J₁, J₅]

Final Schedule: J₃ → J₁ → J₅ Total Profit: 27 + 100 + 15 = 142

Implementation Deep Dive

Let's implement the algorithm with careful attention to correctness, efficiency, and edge cases.

job_scheduling.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
from typing import List, Tuple, Optional
 
class Job:
    """Represents a job with profit and deadline."""
    def __init__(self, id: str, profit: int, deadline: int):
        self.id = id
        self.profit = profit
        self.deadline = deadline
    
    def __repr__(self):
        return f"Job({self.id}, profit={self.profit}, deadline={self.deadline})"
 
def job_scheduling_with_deadlines(
    jobs: List[Job]
) -> Tuple[List[Job], int, List[Optional[Job]]]:
    """
    Schedules jobs to maximize profit under deadline constraints.
    
    Args:
        jobs: List of jobs, each with id, profit, and deadline
        
    Returns:
        Tuple of (scheduled_jobs, total_profit, schedule_array)
        where schedule_array[i] is the job scheduled in slot i (0-indexed)
    """
    if not jobs:
        return [], 0, []
    
    # Step 1: Sort jobs by profit in decreasing order
    sorted_jobs = sorted(jobs, key=lambda j: j.profit, reverse=True)
    
    # Step 2: Find maximum deadline to determine number of slots
    max_deadline = max(job.deadline for job in jobs)
    
    # Step 3: Initialize slots (0-indexed, so slots[i] represents slot i+1)
    # Using None to indicate a free slot
    slots: List[Optional[Job]] = [None] * max_deadline
    
    scheduled_jobs: List[Job] = []
    total_profit: int = 0
    
    # Step 4: Process each job in profit order
    for job in sorted_jobs:
        # Try to find the latest available slot for this job
        # Check from deadline-1 down to 0 (converting to 0-indexed)
        for slot in range(min(job.deadline, max_deadline) - 1, -1, -1):
            if slots[slot] is None:
                # Found a free slot - schedule the job
                slots[slot] = job
                scheduled_jobs.append(job)
                total_profit += job.profit
                break
        # If no slot found, job is simply not scheduled
    
    return scheduled_jobs, total_profit, slots
 
def print_schedule(
    slots: List[Optional[Job]], 
    scheduled: List[Job], 
    profit: int
) -> None:
    """Pretty-prints the scheduling result."""
    print("
" + "=" * 50)
    print("SCHEDULE RESULT")
    print("=" * 50)
    
    print("
Time Slot Assignments:")
    for i, job in enumerate(slots):
        slot_num = i + 1
        if job:
            print(f"  Slot {slot_num}: {job.id} (profit: {job.profit})")
        else:
            print(f"  Slot {slot_num}: [empty]")
    
    print(f"
Scheduled Jobs: {[j.id for j in scheduled]}")
    print(f"Total Profit: {profit}")
    print("=" * 50)
 
 
# Example usage
if __name__ == "__main__":
    jobs = [
        Job("J1", 100, 2),
        Job("J2", 19, 1),
        Job("J3", 27, 2),
        Job("J4", 25, 1),
        Job("J5", 15, 3),
    ]
    
    scheduled, profit, slots = job_scheduling_with_deadlines(jobs)
    print_schedule(slots, scheduled, profit)

Key Implementation Details:

Sorting by profit (decreasing): This ensures we always consider the most valuable jobs first, which is the core greedy choice.
Slot indexing: We use 0-indexed arrays but conceptually work with 1-indexed time slots. slots[i] represents time slot i+1.
Latest slot search: The inner loop for slot in range(deadline-1, -1, -1) searches from the deadline backward to slot 1, implementing the "latest slot first" principle.
Boundary handling: min(job.deadline, max_deadline) ensures we don't access out-of-bounds when a job's deadline exceeds the number of slots (though in the standard problem, deadlines are bounded).
Graceful skipping: Jobs that can't be scheduled are simply passed over—no error, no special handling needed.

Correctness Proof: Why Greedy Works

The greedy algorithm's correctness isn't obvious. Why should processing jobs by profit give an optimal solution? Many greedy approaches fail—what makes this one work?

We'll prove correctness using the exchange argument, showing that any optimal solution can be transformed into the greedy solution without losing profit.

Theorem Statement

The greedy algorithm for job scheduling with deadlines produces an optimal solution—a feasible schedule with maximum total profit.

Proof by Exchange Argument:

Let G be the greedy solution and O be any optimal solution.

Claim 1: The greedy solution is feasible.

By construction, the algorithm only schedules a job when it finds a free slot within the job's deadline. Each job gets at most one slot, and each slot gets at most one job. Therefore, G is always a valid feasible schedule.

Claim 2: The set of jobs in G has maximum profit.

Suppose for contradiction that O contains a set of jobs with strictly greater total profit than G.

Consider the jobs sorted by decreasing profit: J₁, J₂, ..., Jₙ.

Let Jᵢ be the first job (highest profit) where G and O differ. There are two cases:

Case 1: Jᵢ ∈ G but Jᵢ ∉ O

This means the greedy algorithm scheduled Jᵢ, but the optimal solution didn't include it. We can modify O:

Add Jᵢ to O by placing it in the slot used by G
This slot must be free in O (or occupied by a lower-profit job that we can remove)
The modified O has equal or higher profit, still optimal
This contradicts Jᵢ being the first difference

Case 2: Jᵢ ∉ G but Jᵢ ∈ O

This means O includes Jᵢ but the greedy algorithm didn't schedule it. When the greedy algorithm considered Jᵢ, all slots in [1, dᵢ] were occupied by jobs J₁, ..., Jᵢ₋₁ (all have higher profit).

In O, Jᵢ occupies some slot s ≤ dᵢ. One of the higher-profit jobs that G scheduled in [1, dᵢ] must be missing from O (since slots are limited). Call this job Jₖ where k < i (so Jₖ has higher profit than Jᵢ).

We can exchange: remove Jᵢ from O and add Jₖ in slot s. Since Jₖ has deadline ≥ dᵢ (it was schedulable in G), slot s is valid. This exchange increases O's profit, contradicting O's optimality.

Conclusion: No such first difference can exist. Therefore, G and O must select the same jobs, and G achieves optimal profit. ∎

The Exchange Argument Pattern

This proof follows a classic template: assume an optimal solution differs from greedy, find the first difference, show you can exchange to improve or match the optimal solution. This pattern applies to many greedy proofs—activity selection, Huffman coding, and more.

Time Complexity Analysis

Let's analyze the time complexity of our algorithm rigorously.

Time Complexity Breakdown
Operation	Time Complexity	Explanation
Sort jobs by profit	O(n log n)	Standard comparison-based sort
Find max deadline	O(n)	Single pass through all jobs
Initialize slots array	O(d)	Where d = max deadline
Main scheduling loop	O(n × d)	n jobs, each checks up to d slots
Total	O(n log n + n × d)	Dominated by larger term

Detailed Analysis:

The naive implementation has complexity O(n log n + n × d), where:

n = number of jobs
d = maximum deadline

In many practical scenarios, d is bounded (e.g., d ≤ n since scheduling more than n days for n jobs is unnecessary). This gives O(n log n + n²) = O(n²) worst case.

Optimization with Disjoint-Set Union (Union-Find):

We can improve the slot-finding step using a clever Union-Find optimization:

Create a parent array where parent[i] initially points to itself
When slot i is filled, union it with slot i-1
To find the next available slot ≤ d, use find(d) which tells you the highest available slot

This reduces the slot search from O(d) to O(α(d)) amortized (nearly constant), giving O(n log n + n × α(n)) ≈ O(n log n) total.

job_scheduling_optimized.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class UnionFind:
    """Union-Find data structure for efficient slot finding."""
    
    def __init__(self, n: int):
        # parent[i] = the highest available slot <= i
        # Initially, slot i is available, so parent[i] = i
        self.parent = list(range(n + 1))
    
    def find(self, x: int) -> int:
        """Find the highest available slot <= x."""
        if x <= 0:
            return 0  # No valid slot
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]
    
    def use_slot(self, slot: int) -> None:
        """Mark slot as used by unioning with slot-1."""
        if slot > 0:
            self.parent[slot] = self.find(slot - 1)
 
def job_scheduling_optimized(jobs: List[Job]) -> Tuple[List[Job], int]:
    """
    Optimized job scheduling using Union-Find for O(n log n) complexity.
    """
    if not jobs:
        return [], 0
    
    # Sort by profit descending
    sorted_jobs = sorted(jobs, key=lambda j: j.profit, reverse=True)
    max_deadline = max(job.deadline for job in jobs)
    
    # Initialize Union-Find
    uf = UnionFind(max_deadline)
    
    scheduled: List[Job] = []
    total_profit: int = 0
    slots: List[Optional[Job]] = [None] * (max_deadline + 1)
    
    for job in sorted_jobs:
        # Find the highest available slot <= deadline
        available_slot = uf.find(job.deadline)
        
        if available_slot > 0:
            # Schedule job in this slot
            slots[available_slot] = job
            scheduled.append(job)
            total_profit += job.profit
            uf.use_slot(available_slot)
    
    return scheduled, total_profit

Complexity Improvement

The Union-Find optimization reduces overall complexity from O(n × d) to O(n × α(n)), where α is the inverse Ackermann function—essentially constant for all practical inputs. This makes the algorithm efficient even for large deadline values.

Variations and Extensions

The job scheduling pattern extends to numerous variations, each with practical applications:

Common Variations

•Variable Processing Times: Jobs take different amounts of time. The greedy approach extends using weighted job scheduling (often requires DP for optimality).
•Multiple Processors: Schedule jobs on k machines instead of one. The problem becomes a variant of load balancing.
•Penalties Instead of Profits: Minimize total penalty for missed deadlines rather than maximizing profit—mathematically equivalent by transformation.
•Release Times: Jobs become available at different times, not all at the start. Requires online algorithms or modified greedy approaches.
•Preemption Allowed: Jobs can be interrupted and resumed. Changes the problem structure significantly—different algorithms apply.
•Dependencies: Some jobs must complete before others can start. Introduces topological ordering constraints.

Real-World Applications:

Domain	Application	Mapping
Cloud Computing	Serverless function scheduling	Functions = jobs, SLA = deadline, Revenue = profit
Manufacturing	Production line scheduling	Orders = jobs, Due dates = deadlines, Revenue = profit
Healthcare	Operating room scheduling	Surgeries = jobs, Urgency = deadline, Priority = profit
Finance	Trade execution	Orders = jobs, Market close = deadline, Expected gain = profit
Academia	Paper submission	Papers = jobs, Conference deadline = deadline, Impact = profit

Interview Perspective

Job scheduling with deadlines appears frequently in technical interviews, often disguised with different terminology. Here's how to recognize and approach it:

Recognition Signals

•Items have values AND constraints
•Each item needs a 'slot' or 'resource'
•Limited resources (time, space, slots)
•Goal is maximizing total value
•Items are independent (no dependencies)

Interview Tips

•Start with the naive O(n²) solution
•Explain the greedy intuition clearly
•Mention the Union-Find optimization
•Discuss edge cases (no jobs, all same deadline)
•Be ready to prove correctness if asked

Common Interview Disguises

"Maximum tasks before expiration", "Optimal project selection", "Meeting room revenue", "Server task allocation"—these are all job scheduling variants. The telltale signs are: maximize value, limited slots, items have constraints on which slots they can use.

Summary: Job Scheduling Pattern

Let's consolidate the key insights from job scheduling with deadlines:

Key Takeaways

•Problem: Select and schedule jobs with deadlines to maximize profit, where each job takes one time unit
•Greedy Strategy: Sort by profit descending, schedule each job in the latest available slot within its deadline
•Why It Works: Exchange argument proves no better solution exists—high-profit jobs should always be preferred
•Time Complexity: O(n²) naive, O(n log n) with Union-Find optimization
•Space Complexity: O(d) where d is the maximum deadline
•Pattern Recognition: Look for maximize value + limited resources + item constraints

The Deeper Lesson:

Job scheduling exemplifies a fundamental greedy principle: when resources are limited and items have both value and flexibility, prioritize high-value items while preserving flexibility for others. The "latest slot first" heuristic is a manifestation of this principle—don't waste flexibility on items that don't need it.

This pattern extends beyond scheduling to resource allocation, assignment problems, and capacity planning—anywhere you must select from constrained options to maximize value.

Page Complete

You've mastered the job scheduling with deadlines pattern. Next, we'll explore the minimum coins problem—another greedy pattern where local optimization leads to global optimality, but only under specific conditions.