Interval Scheduling (Minimizing Lateness)
Given a set of jobs with durations and deadlines, schedule them on a single machine to minimize the maximum lateness. Lateness is defined as the amount of time by which a job's finish time exceeds its deadline.
Interval Scheduling
Ready
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
When you have multiple assignments with deadlines, which one should you do first to avoid being very late for any single one? Intuitively, working on the assignment due soonest (Earliest Deadline First) seems best.
This greedy strategy turns out to be optimal. By clearing the most urgent tasks first, you minimize the risk of any task interfering with a later but tighter deadline.
Concept
The Greedy Choice: Sort jobs by their deadline in ascending order.
Schedule the jobs back-to-back starting from time t=0. This approach minimizes the maximum lateness across all jobs. Note that it does not necessarily maximize the number of jobs done (that's Activity Selection) or minimize total completion time.
How it Works
- Sort: Order all jobs by deadline (d1 ≤ d2 ≤ ... ≤ dn).
- Initialize: Set current time
start_time = 0. - Iterate: For each job in sorted order:
- Assign the job to start at
start_time. - Finish time =
start_time + duration. - Calculate Lateness =
max(0, finish_time - deadline). - Update
start_time = finish_time.
- Assign the job to start at
- Result: The maximum lateness found is the minimum possible max lateness.
Step-by-Step Breakdown
Jobs: A(Len:3, Due:6), B(Len:2, Due:8), C(Len:1, Due:9), D(Len:4, Due:9)
- Sort by Deadline: A(6), B(8), C(9), D(9).
- Job A: Start 0, Finish 3. Late: max(0, 3-6)=0. Time=3.
- Job B: Start 3, Finish 5. Late: max(0, 5-8)=0. Time=5.
- Job C: Start 5, Finish 6. Late: max(0, 6-9)=0. Time=6.
- Job D: Start 6, Finish 10. Late: max(0, 10-9)=1. Time=10.
- Max Lateness: 1.
When to Use
- Scheduling tasks with hard deadlines to avoid significant delays.
- Project management critical paths.
When NOT to Use
- If minimizing total lateness (sum) is required (EDF is not always optimal for sum).
- If jobs have release times (can't start before t).
How to Identify
Keywords: "Minimize maximum lateness", "Deadlines", "Single resource".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.