What is Job Sequencing with Deadlines?
Learn the greedy job sequencing with deadlines algorithm: sort by profit, slot latest-first, and maximize total profit under deadlines.
Expected Interview Answer
Job sequencing with deadlines is a greedy scheduling problem where each job has a profit and a deadline, only one job can run per time slot, and the goal is to select and order jobs to maximize total profit while respecting every chosen job’s deadline.
The standard greedy solution sorts all jobs by profit in descending order, then for each job, places it in the latest free time slot at or before its deadline, using a slot array or a disjoint-set (union-find) structure to find that slot quickly. Because higher-profit jobs are considered first and always get the latest possible slot that still meets their deadline, earlier slots stay open for other high-value jobs that have tighter deadlines. This greedy-by-profit, place-latest-possible strategy is provably optimal for this problem, running in O(n log n) for the sort plus near-linear slot lookups with union-find. It models real scheduling situations where slots are scarce, deadlines are hard constraints, and the objective is to maximize value rather than minimize lateness.
- Maximizes total profit under hard deadline constraints
- Greedy-by-profit ordering is provably optimal
- Union-find speeds up slot lookup to near O(n)
- Models real resource-scarce scheduling problems
AI Mentor Explanation
A broadcaster has limited ad slots before a match and must pick which sponsors to air, each sponsor paying a different fee and requiring their ad to run by a certain over. The scheduler sorts sponsors by fee, highest first, and for each one books the latest available ad slot that still meets that sponsor’s over deadline, leaving earlier slots free for sponsors with tighter deadlines. A cheap sponsor with a late deadline never bumps a high-paying sponsor out of a slot it desperately needs early. This greedy, latest-slot-first placement is exactly how job sequencing with deadlines maximizes total sponsorship revenue.
Step-by-Step Explanation
Step 1
Sort jobs by profit descending
Process the highest-value jobs first so they get first claim on their preferred slots.
Step 2
Find the latest free slot at or before the deadline
For each job, search backward from its deadline for an open time slot.
Step 3
Assign the job if a slot exists
If a free slot is found at or before the deadline, occupy it and add the job’s profit to the total.
Step 4
Skip the job if no slot remains
If every slot at or before the deadline is taken, the job is dropped and yields no profit.
What Interviewer Expects
- Explain the greedy rule: sort by profit descending, place in latest feasible slot
- Justify why latest-slot placement (not earliest) preserves flexibility for future jobs
- State time complexity: O(n log n) sort, with union-find slot lookup near O(n)
- Give a real use case: limited resource slots with hard deadlines and variable value
Common Mistakes
- Sorting by deadline instead of profit
- Placing a job in the earliest available slot instead of the latest
- Forgetting a job with no available slot before its deadline must be dropped, not scheduled late
- Using a linear scan for slot lookup instead of union-find, missing the efficiency gain
Best Answer (HR Friendly)
“Job sequencing with deadlines is about picking which jobs to run when you have more jobs than time slots and each job has a profit and a deadline. I sort jobs by profit, highest first, and slot each one into the latest available time before its deadline, which keeps earlier slots free for jobs that need them and maximizes total profit.”
Code Example
def job_sequencing(jobs):
# jobs: list of (job_id, deadline, profit)
jobs = sorted(jobs, key=lambda j: j[2], reverse=True)
max_deadline = max(j[1] for j in jobs)
slots = [None] * (max_deadline + 1) # index 0 unused
total_profit = 0
scheduled = []
for job_id, deadline, profit in jobs:
for slot in range(min(deadline, max_deadline), 0, -1):
if slots[slot] is None:
slots[slot] = job_id
total_profit += profit
scheduled.append(job_id)
break
return scheduled, total_profitFollow-up Questions
- How would you speed up slot lookup with a union-find (disjoint-set) structure?
- How does this problem relate to activity selection and interval scheduling?
- What happens if two jobs have the same profit but different deadlines?
- How would you adapt this to allow multiple slots per time unit?
MCQ Practice
1. In the standard greedy job sequencing algorithm, jobs are first sorted by what?
Sorting by profit descending ensures the most valuable jobs get first claim on a feasible slot.
2. Why does the algorithm place each job in the latest free slot at or before its deadline, rather than the earliest?
Placing a job as late as possible preserves earlier slots as options for jobs that may have tighter deadlines.
3. What happens to a job if no slot is free at or before its deadline?
If every feasible slot is taken, the job simply cannot be scheduled and is skipped.
Flash Cards
What two attributes does each job have in job sequencing with deadlines? — A profit and a deadline (the latest slot by which it must run).
What is the greedy sort order for job sequencing with deadlines? — Profit descending, highest-value jobs considered first.
Where does the algorithm place a job among free slots? — The latest available slot at or before its deadline.
What structure speeds up finding the next free slot efficiently? — A union-find (disjoint-set) structure, giving near-linear slot lookup.