Faangprep Logo
Log inStart free
Browse curriculum

Interval Scheduling (Minimizing Lateness)

Interval scheduling to minimize lateness orders jobs, each with a duration and a deadline, on a single machine so that the maximum lateness is as small as possible. Lateness is the amount of time by which a job's finish time exceeds its deadline.

Every job must run, one at a time, so the only decision is the order. A job that finishes after its deadline is late by the difference — and the goal is to make the largest of those differences as small as it can be.

READY

J1

J2

J3

J4

J5

Worst overrun

0

 

Five jobs, one machine. Every one of them has to run.

Next

Sort by deadline, earliest first. That order is the whole strategy.

Run in order of

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

  1. Sort: Order all jobs by deadline (d1 ≤ d2 ≤ ... ≤ dn).
  2. Initialize: Set current time start_time = 0.
  3. 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.
  4. 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)

  1. Sort by Deadline: A(6), B(8), C(9), D(9).
  2. Job A: Start 0, Finish 3. Late: max(0, 3-6)=0. Time=3.
  3. Job B: Start 3, Finish 5. Late: max(0, 5-8)=0. Time=5.
  4. Job C: Start 5, Finish 6. Late: max(0, 6-9)=0. Time=6.
  5. Job D: Start 6, Finish 10. Late: max(0, 10-9)=1. Time=10.
  6. 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".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Huffman Coding

Next

Job Sequencing

Frequently Asked Questions

What is the goal of Interval Scheduling?

To select the largest possible set of mutually non-overlapping intervals (tasks) from a given collection.

Interval Scheduling vs Activity Selection?

They are essentially the same problem! Both rely on sorting by finish time to find the optimal Greedy solution.

What if they have different priorities?

If tasks have "Weights" or "Profits," the problem becomes "Weighted Interval Scheduling," which requires Dynamic Programming instead of Greedy.