Loading…

mediumGreedySometimes asked

Job Sequencing with Deadlines

Greedy Algorithms · 11 of 23 · 11 min

You are given n jobs. Each job i has a deadline deadline[i] and a profit profit[i], and takes exactly one unit of time to run. A single machine runs one job per time unit, starting at time 1.

A job earns its profit only if it is scheduled to finish at or before its deadline. Choose a subset and an ordering that maximises the total profit of on-time jobs. Return the number of jobs done and the total profit (or just the maximum profit).

In plain English

Time is divided into unit slots 1, 2, 3, …. Each job needs one slot no later than its deadline. We're choosing which jobs to run and when, to maximise profit. Since every job takes the same time, the only thing that distinguishes them is profit and how tight their deadline is — so we prioritise profit and use deadlines only to decide whether a slot is still available.

Examples

Example 1

Input: jobs = [(deadline=2, profit=100), (1,19), (2,27), (1,25), (3,15)]
Output: count = 3, profit = 142
Note: Sorted by profit: 100(d2),27(d2),25(d1),19(d1),15(d3). Place 100→slot2, 27→slot1, 25→d1 full skip, 19→skip, 15→slot3. Profit 100+27+15 = 142.

Example 2

Input: jobs = [(1,40), (1,30)]
Output: count = 1, profit = 40
Note: Both need slot 1; the higher-profit 40 wins, 30 is dropped.

Example 3

Input: jobs = [(3,20), (1,10), (1,40), (1,30)]
Output: count = 2, profit = 60
Note: 40→slot1, 20→slot3 (latest free ≤3), 30 and 10 want slot1 which is taken → dropped. 40+20 = 60.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ deadline[i] ≤ n (a deadline beyond n is never more useful than n)
1 ≤ profit[i] ≤ 10⁹ (sum can exceed a 32-bit int → accumulate profit in a long)
Each job is unit time and can be dropped if it can't be scheduled on time

Clarifying questions4First question: Does every job take the same amount of time?Explore questions

Q1.Does every job take the same amount of time?
Yes — unit time. That's the assumption that makes the greedy correct; arbitrary durations would need DP or flow.
Q2.Can I skip jobs that can't be scheduled on time?
Yes. We maximise profit over the jobs we *can* fit; an unschedulable job simply earns nothing.
Q3.Can total profit overflow a 32-bit integer?
With up to 10⁵ jobs at 10⁹ each, the sum reaches 10¹⁴ — well past int range. I accumulate in a long.
Q4.Are deadlines bounded by n?
Effectively yes — a deadline larger than n can't help since there are at most n slots worth using. I cap maxDeadline at n.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Each unit-time job earns its profit only if it runs at or before its deadline. Greedily process jobs from highest profit to lowest, and place each one in the LATEST free time slot at or before its deadline. Scheduling late leaves the early slots open for tighter-deadline jobs that come later. With a simple slot array the scan is O(n·maxDeadline); with disjoint-set union (path-compressed 'find the latest free slot') it's effectively O(n log n).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you combine TWO greedy ideas — sort by profit descending AND place each job in the latest free slot before its deadline — and can argue why scheduling late is what makes it optimal.

Where candidates slip

Placing jobs in the EARLIEST free slot (which needlessly blocks urgent jobs), or sorting by deadline instead of profit, or forgetting that jobs are unit-time.

How to stand out

Explain the exchange argument: filling the latest slot never hurts a future job that an earlier slot could have served, and processing high-profit first means any unavoidable drop removes the least valuable job. Then upgrade the O(n·D) slot scan to union-find for near-linear time.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Sort by Profit + Slot Array (Baseline-to-Solid)	`O(n log n + n·maxDeadline)`	`O(maxDeadline)`	Start here: it's the clear, correct greedy. State its O(n·maxDeadline) cost, then offer union-find to speed the slot lookup.	Read
2	Profit Sort + Union-Find Slot Lookup (Optimal)Optimal	`O(n log n + n·α(n))`	`O(maxDeadline)`	Bring this up after the slot-array version to kill the O(n·maxDeadline) worst case — phrase it as 'union-find as a next-free-slot pointer'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewSort jobs by profit descendingMore jobs?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Sort by Profit + Slot Array (Baseline-to-Solid)

TimeO(n log n + n·maxDeadline)SpaceO(maxDeadline)

Start here: it's the clear, correct greedy. State its O(n·maxDeadline) cost, then offer union-find to speed the slot lookup.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Every job is the same length, so the only reasons to prefer one over another are its profit and how soon it's due. Which should drive the order you consider jobs?

2Hint 2Explore hint

Sort jobs by profit descending. For each job, you want to run it as LATE as possible without missing its deadline. Why late and not early?

3Hint 3Explore hint

Keep a boolean slot array of size maxDeadline. For the current job, scan from its deadline downward to slot 1 and grab the first free slot; if none, drop the job.

A · Core idea

Sort jobs by profit, highest first. Maintain slot[1..maxDeadline], all free. For each job, search from min(maxDeadline, deadline) down to 1 for a free slot; if you find one, occupy it and bank the profit, otherwise drop the job.

Why sort by profit descending. If a slot conflict ever forces us to drop a job, we want the dropped job to be the least valuable one. Considering jobs from most to least profitable guarantees that whenever we're forced to skip, every job already placed is at least as valuable — so the loss is minimised. This is the 'most valuable first' half of the greedy.

Why place each job in the LATEST free slot, not the earliest. This is the subtle, decisive choice. A job with deadline d can run in any slot 1..d. If we put it in the earliest free slot, we consume an early slot that a later-considered, tighter-deadline job might desperately need (that urgent job can only use early slots). By placing the current job as late as its deadline permits, we keep the early slots open as long as possible. Filling from the back never costs us anything: any future job that could have used the slot we took could equally use an earlier still-free slot, because that future job's deadline is ≥ the slot we filled. This is the exchange argument — swapping a late placement for an earlier one never increases the number of feasible jobs.

Why unit time is essential. Because each job occupies exactly one slot, feasibility reduces to 'is any slot ≤ deadline free?'. There's no packing of variable lengths, no fragmentation — that clean structure is precisely what lets the greedy be optimal. Drop the unit-time assumption and the argument collapses; you'd need DP or flow.

The cost wrinkle. The backward scan per job can walk up to maxDeadline slots, so a worst case (many jobs with large deadlines all colliding) is O(n·maxDeadline). That's fine for moderate inputs, but the next approach removes it.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

jobs sorted by profit: (d2,100),(d2,27),(d1,25),(d1,19),(d3,15)

Array state

(d2,100)

take slot 2

[0]

[1]

slot ↓

100

[2]

Current pointerResolved stateNot processed

Final resultcount = 3, profit = 142

C · Code with teaching comments

Reference implementation previewpublic int[] jobScheduling(int[] deadline, int[] profit) { int n = deadline.length; Integer[] idx = new Integer[n]; for (int i = 0; i < n; i++) idx[i] = i; Arrays.sort(idx, (a, b) -> Integer.compare(profit[b], profit[a])); // profit descExplore the full code

solution.javaJava

Sort by Profit + Slot Array (Baseline-to-Solid) — reference

4 teaching notes

1
public int[] jobScheduling(int[] deadline, int[] profit) {
2
    int n = deadline.length;
3
    Integer[] idx = new Integer[n];
4
    for (int i = 0; i < n; i++) idx[i] = i;
5
    Arrays.sort(idx, (a, b) -> Integer.compare(profit[b], profit[a])); // profit desc
6
    int maxD = 0;
7
    for (int d : deadline) maxD = Math.max(maxD, d);
8
    boolean[] slot = new boolean[maxD + 1]; // 1-indexed
9
    int count = 0;
10
    long totalProfit = 0;
11
    for (int i = 0; i < n; i++) {
12
        int j = idx[i];
13
        // Scan from the deadline DOWNWARD — placing late keeps early slots free for
14
        // tighter-deadline jobs.
15
        for (int t = Math.min(maxD, deadline[j]); t >= 1; t--) {
16
            if (!slot[t]) {
17
                // Occupy the latest free slot; this job is now on time.
18
                slot[t] = true;
19
                count++;
20
                // Accumulate in a long — profits can sum past int range.
21
                totalProfit += profit[j];
22
                break;
23
            }
24
        }
25
    }
26
    return new int[]{count, (int) Math.min(totalProfit, Integer.MAX_VALUE)};
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n log n + n·maxDeadline) timeO(maxDeadline) spaceOpen the invariant and proofExplore the proof

Two greedy choices stack: profit-descending order means any forced drop sacrifices the cheapest job, and latest-slot placement means a placement never steals a slot a tighter-deadline job uniquely needs. The latest-slot rule is the non-obvious one — most people reach for the earliest slot and quietly lose optimality.

ComplexityO(n log n + n·maxDeadline) time, O(maxDeadline) space — Sorting is O(n log n). For each of the n jobs, the backward scan for a free slot costs up to maxDeadline in the worst case, giving O(n·maxDeadline). The slot array is O(maxDeadline) space.

E · Edge cases and pitfalls7all deadline = 1 — Only slot 1 exists; the single highest-profit job is taken, the rest dropped.Explore edge cases

Edge cases handled

all deadline = 1Only slot 1 exists; the single highest-profit job is taken, the rest dropped.
all distinct large deadlinesEvery job finds its own slot → all scheduled, profit = sum.
n jobs, all deadline = nAll fit (n slots) → count n; worst case for the O(n·maxD) scan.

Pitfalls

Placing jobs in the earliest free slot — blocks urgent (tight-deadline) jobs considered later.
Sorting by deadline instead of profit — you can end up keeping cheap jobs over valuable ones.
Summing profit in an int — overflows when many high-profit jobs are scheduled.
Treating jobs as multi-unit — the greedy only holds for unit-time jobs.

03.2

Approach 2 of 2 · Optimal

Profit Sort + Union-Find Slot Lookup (Optimal)

TimeO(n log n + n·α(n))SpaceO(maxDeadline)

Bring this up after the slot-array version to kill the O(n·maxDeadline) worst case — phrase it as 'union-find as a next-free-slot pointer'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The slow part of the slot-array version is the backward scan for a free slot. Could you jump straight to the latest free slot ≤ d in almost O(1)?

2Hint 2Explore hint

Use a disjoint-set structure where parent[t] points to the latest free slot at or before t. find(d) returns it directly.

3Hint 3Explore hint

After assigning slot t, union it to t−1 so future finds skip past the now-occupied slot. Path compression makes this near-constant amortised.

A · Core idea

Keep the same two greedy decisions — profit-descending order, latest-slot placement — but replace the linear backward scan with a disjoint-set union (DSU) that answers 'what's the latest free slot ≤ d?' in near-constant time.

The DSU-as-pointer idea. Initialise parent[t] = t for t in 0..maxDeadline. The invariant is: find(t) returns the largest still-free slot index that is ≤ t (or 0 if none remain). For a job with deadline d, call find(d). If it returns a slot s ≥ 1, that slot is free — assign the job there, bank the profit, and then union(s, s−1) by setting parent[s] = s − 1. That union makes every future find that lands on s skip down to the latest free slot below s. Path compression flattens the chains so repeated finds are amortised near O(1).

Why this preserves correctness. The greedy logic is unchanged: we still take jobs most-profitable-first and still place each in the latest free slot ≤ its deadline — the exchange argument from the slot-array approach applies verbatim. DSU only changes how fast we locate that latest free slot; it never changes which slot we pick. find(d) returns exactly the slot the backward scan would have found (the highest free index ≤ d), and pointing s to s−1 after use is just an O(1) way to mark s occupied and remember where the next free slot is.

Why the speed-up matters. The slot-array scan is O(n·maxDeadline) in the worst case — pathological when many jobs share large deadlines and collide. DSU collapses each lookup to amortised α(n) (the inverse Ackermann function, ≤ 4 for any realistic n), so the whole scheduling phase is effectively linear and the algorithm is dominated by the initial O(n log n) sort.

Slot 0 as the sentinel. Index 0 represents 'no free slot available'. When find(d) returns 0, every slot ≤ d is taken and the job is dropped. Unioning the last used slot down toward 0 naturally funnels exhausted deadlines to this sentinel.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

jobs by profit: (d3,20),(d1,40),(d1,30),(d1,10)

Array state

init

parent[t] = t

slot0 ↓

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final resultcount = 2, profit = 60

C · Code with teaching comments

solution.javaJava

Profit Sort + Union-Find Slot Lookup (Optimal) — optimal

5 teaching notes

1
private int[] parent;
2
 
3
private int find(int x) {
4
    if (parent[x] != x) parent[x] = find(parent[x]); // path compression
5
    return parent[x];
6
}
7
 
8
public int[] jobScheduling(int[] deadline, int[] profit) {
9
    int n = deadline.length;
10
    Integer[] idx = new Integer[n];
11
    for (int i = 0; i < n; i++) idx[i] = i;
12
    Arrays.sort(idx, (a, b) -> Integer.compare(profit[b], profit[a])); // profit desc
13
    int maxD = 0;
14
    for (int d : deadline) maxD = Math.max(maxD, d);
15
    parent = new int[maxD + 1];
16
    for (int t = 0; t <= maxD; t++) parent[t] = t; // slot 0 = sentinel
17
    int count = 0;
18
    long totalProfit = 0;
19
    for (int i = 0; i < n; i++) {
20
        int j = idx[i];
21
        // Jump straight to the latest free slot ≤ the job's deadline.
22
        int slot = find(Math.min(maxD, deadline[j]));
23
        if (slot > 0) {
24
            parent[slot] = slot - 1; // mark used, forward to previous free
25
            count++;
26
            // Long accumulator to avoid overflow on summed profits.
27
            totalProfit += profit[j];
28
        }
29
    }
30
    return new int[]{count, (int) Math.min(totalProfit, Integer.MAX_VALUE)};
31
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.31 lines

D · Why it works and complexityO(n log n + n·α(n)) timeO(maxDeadline) spaceOpen the invariant and proofExplore the proof

Union-find shines as a 'next available resource' pointer: each slot, once used, forwards future queries to the next free slot below it. This 'point to the previous free index' trick recurs in problems like painting/booking intervals and 'smallest available id'. The greedy proof is identical to the slot-array version — DSU is purely an accelerator for the latest-free-slot query.

ComplexityO(n log n + n·α(n)) time, O(maxDeadline) space — Sorting is O(n log n). Each job does one find (and one union), each near-O(α(n)) ≈ O(1) amortised with path compression, so the scheduling phase is effectively O(n·α(n)). Space is O(maxDeadline) for the parent array.

E · Edge cases and pitfalls7all deadline = 1 — find(1) succeeds once, then parent[1]=0 → every later job finds slot 0 and is dropped.Explore edge cases

Edge cases handled

all deadline = 1find(1) succeeds once, then parent[1]=0 → every later job finds slot 0 and is dropped.
deadlines distinct & ampleEach find hits a fresh slot → all jobs scheduled.
duplicate max profitsTie order doesn't affect total profit; both get distinct slots if available.

Pitfalls

Forgetting the slot-0 sentinel — find could return an invalid slot and you'd schedule a job nowhere.
Skipping path compression — finds degrade toward O(maxDeadline) and you lose the speed-up.
Unioning to slot+1 instead of slot−1 — you must forward to the EARLIER free slot, not later.
Capping deadline incorrectly — clamp to maxDeadline so find stays in bounds.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewprivate int[] parent; private int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); // path compression return parent[x];Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Earliest-slot instead of latest-slot placement

Filling early slots consumes capacity that tight-deadline jobs (considered later) uniquely need. Placing each job as late as its deadline allows keeps early slots open and is what makes the greedy optimal.

Explore the code comparison

Don't write this

for (int t = 1; t <= Math.min(maxD, deadline[j]); t++) {
    if (!slot[t]) { slot[t] = true; break; }   // earliest free — WRONG
}

Write this instead

for (int t = Math.min(maxD, deadline[j]); t >= 1; t--) {
    if (!slot[t]) { slot[t] = true; break; }   // latest free — correct
}

Sorting by deadline rather than profit

Deadline order can place a low-profit job into a slot a high-profit job needed, reducing total profit. Profit-descending order guarantees any forced drop is the least valuable job.

Explore the code comparison

Don't write this

Arrays.sort(idx, (a, b) -> Integer.compare(deadline[a], deadline[b]));

Write this instead

Arrays.sort(idx, (a, b) -> Integer.compare(profit[b], profit[a]));

Profit accumulated in int

With up to 10⁵ jobs at 10⁹ profit each, the total reaches ~10¹⁴ and overflows a 32-bit int silently. Use a long (Java) — Python ints are unbounded.

Explore the code comparison

Don't write this

int totalProfit = 0;
totalProfit += profit[j];   // overflows

Write this instead

long totalProfit = 0;
totalProfit += profit[j];   // safe

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort by profit desc, place each job in the latest free slot ≤ its deadline

Code pattern to memorize

sort jobs by profit desc
slot[1..maxDeadline] = free
for job in jobs:
    for t from min(maxDeadline, job.deadline) down to 1:
        if slot[t] free: assign job to t; break
# union-find: find(d) returns latest free slot <= d in near-O(1)

Rules to remember

1Process jobs by profit descending — commit to the most valuable jobs first.
2Place each job as late as possible (latest free slot ≤ deadline), never early — this preserves earlier slots for jobs with tighter deadlines.
3Jobs are unit time: each occupies exactly one integer slot, so feasibility is purely 'is there a free slot ≤ deadline?'.
4Slots are 1-indexed up to maxDeadline; a job with deadline d can use any of slots 1..d.
5For speed, replace the inner backward scan with union-find where find(d) jumps straight to the latest free slot ≤ d, then unions it to d−1.

Use this pattern when

Unit-time jobs, each with a deadline and a profit; maximise total profit of on-time jobs
A single machine processing one job per time unit
You can drop jobs entirely (no partial credit) and order is free within deadlines
Classic 'sort by value, fit greedily into latest slot' scheduling

Choose another pattern when

Jobs have arbitrary (non-unit) durations → this greedy breaks; use DP / flow
You must run every job (no dropping) → feasibility/ordering problem, not selection
Objective is minimise lateness / weighted completion time → different scheduling theory
Multiple machines in parallel → load-balancing, not single-slot greedy

Interview takeaway

Two greedy decisions combine here: take the most profitable jobs first (so a forced drop sacrifices the cheapest job), and schedule each as late as its deadline allows (so early slots stay open for urgent jobs). The latest-free-slot lookup is the textbook use of union-find as a 'next available pointer', turning an O(n·D) scan into near-linear time.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical 'value-first greedy + latest-free-slot' scheduling. Sort by profit descending, schedule each unit job as late as its deadline allows, and use union-find as a next-free-slot pointer for near-linear time. The DSU 'point to previous free index' trick reappears in interval booking and smallest-available-id problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Course Schedule III
Coming soon
Variable durations with deadlines → greedy by deadline + a max-heap to evict the longest course.
Weighted Job Scheduling (variable length)
Coming soon
Non-unit durations break this greedy; sort by finish and DP with binary search instead.
Maximize Profit with K Machines
Coming soon
K parallel slots per time unit — generalise the slot/union-find capacity per timestamp.
Activity Selection
The unweighted sibling — maximise count of compatible intervals via finish-time greedy.

Same pattern

←

Activity Selection

Continue · Next problem

Connect N Ropes with Minimum Cost

mediumGreedySometimes asked

Job Sequencing with Deadlines

Greedy Algorithms · 11 of 23 · 11 min

In plain English

Examples

Example 1

Input: jobs = [(deadline=2, profit=100), (1,19), (2,27), (1,25), (3,15)]
Output: count = 3, profit = 142
Note: Sorted by profit: 100(d2),27(d2),25(d1),19(d1),15(d3). Place 100→slot2, 27→slot1, 25→d1 full skip, 19→skip, 15→slot3. Profit 100+27+15 = 142.

Example 2

Input: jobs = [(1,40), (1,30)]
Output: count = 1, profit = 40
Note: Both need slot 1; the higher-profit 40 wins, 30 is dropped.

Example 3

Input: jobs = [(3,20), (1,10), (1,40), (1,30)]
Output: count = 2, profit = 60
Note: 40→slot1, 20→slot3 (latest free ≤3), 30 and 10 want slot1 which is taken → dropped. 40+20 = 60.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ deadline[i] ≤ n (a deadline beyond n is never more useful than n)
1 ≤ profit[i] ≤ 10⁹ (sum can exceed a 32-bit int → accumulate profit in a long)
Each job is unit time and can be dropped if it can't be scheduled on time

Clarifying questions4First question: Does every job take the same amount of time?Explore questions

Q1.Does every job take the same amount of time?
Yes — unit time. That's the assumption that makes the greedy correct; arbitrary durations would need DP or flow.
Q2.Can I skip jobs that can't be scheduled on time?
Yes. We maximise profit over the jobs we *can* fit; an unschedulable job simply earns nothing.
Q3.Can total profit overflow a 32-bit integer?
With up to 10⁵ jobs at 10⁹ each, the sum reaches 10¹⁴ — well past int range. I accumulate in a long.
Q4.Are deadlines bounded by n?
Effectively yes — a deadline larger than n can't help since there are at most n slots worth using. I cap maxDeadline at n.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you combine TWO greedy ideas — sort by profit descending AND place each job in the latest free slot before its deadline — and can argue why scheduling late is what makes it optimal.

Where candidates slip

Placing jobs in the EARLIEST free slot (which needlessly blocks urgent jobs), or sorting by deadline instead of profit, or forgetting that jobs are unit-time.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Sort by Profit + Slot Array (Baseline-to-Solid)	`O(n log n + n·maxDeadline)`	`O(maxDeadline)`	Start here: it's the clear, correct greedy. State its O(n·maxDeadline) cost, then offer union-find to speed the slot lookup.	Read
2	Profit Sort + Union-Find Slot Lookup (Optimal)Optimal	`O(n log n + n·α(n))`	`O(maxDeadline)`	Bring this up after the slot-array version to kill the O(n·maxDeadline) worst case — phrase it as 'union-find as a next-free-slot pointer'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Sort by Profit + Slot Array (Baseline-to-Solid)

TimeO(n log n + n·maxDeadline)SpaceO(maxDeadline)

Start here: it's the clear, correct greedy. State its O(n·maxDeadline) cost, then offer union-find to speed the slot lookup.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Every job is the same length, so the only reasons to prefer one over another are its profit and how soon it's due. Which should drive the order you consider jobs?

2Hint 2Explore hint

Sort jobs by profit descending. For each job, you want to run it as LATE as possible without missing its deadline. Why late and not early?

3Hint 3Explore hint

Keep a boolean slot array of size maxDeadline. For the current job, scan from its deadline downward to slot 1 and grab the first free slot; if none, drop the job.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

jobs sorted by profit: (d2,100),(d2,27),(d1,25),(d1,19),(d3,15)

Array state

(d2,100)

take slot 2

[0]

[1]

slot ↓

100

[2]

Current pointerResolved stateNot processed

Final resultcount = 3, profit = 142

C · Code with teaching comments

solution.javaJava

Sort by Profit + Slot Array (Baseline-to-Solid) — reference

4 teaching notes

1
public int[] jobScheduling(int[] deadline, int[] profit) {
2
    int n = deadline.length;
3
    Integer[] idx = new Integer[n];
4
    for (int i = 0; i < n; i++) idx[i] = i;
5
    Arrays.sort(idx, (a, b) -> Integer.compare(profit[b], profit[a])); // profit desc
6
    int maxD = 0;
7
    for (int d : deadline) maxD = Math.max(maxD, d);
8
    boolean[] slot = new boolean[maxD + 1]; // 1-indexed
9
    int count = 0;
10
    long totalProfit = 0;
11
    for (int i = 0; i < n; i++) {
12
        int j = idx[i];
13
        // Scan from the deadline DOWNWARD — placing late keeps early slots free for
14
        // tighter-deadline jobs.
15
        for (int t = Math.min(maxD, deadline[j]); t >= 1; t--) {
16
            if (!slot[t]) {
17
                // Occupy the latest free slot; this job is now on time.
18
                slot[t] = true;
19
                count++;
20
                // Accumulate in a long — profits can sum past int range.
21
                totalProfit += profit[j];
22
                break;
23
            }
24
        }
25
    }
26
    return new int[]{count, (int) Math.min(totalProfit, Integer.MAX_VALUE)};
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n log n + n·maxDeadline) timeO(maxDeadline) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7all deadline = 1 — Only slot 1 exists; the single highest-profit job is taken, the rest dropped.Explore edge cases

Edge cases handled

all deadline = 1Only slot 1 exists; the single highest-profit job is taken, the rest dropped.
all distinct large deadlinesEvery job finds its own slot → all scheduled, profit = sum.
n jobs, all deadline = nAll fit (n slots) → count n; worst case for the O(n·maxD) scan.

Pitfalls

Placing jobs in the earliest free slot — blocks urgent (tight-deadline) jobs considered later.
Sorting by deadline instead of profit — you can end up keeping cheap jobs over valuable ones.
Summing profit in an int — overflows when many high-profit jobs are scheduled.
Treating jobs as multi-unit — the greedy only holds for unit-time jobs.

03.2

Approach 2 of 2 · Optimal

Profit Sort + Union-Find Slot Lookup (Optimal)

TimeO(n log n + n·α(n))SpaceO(maxDeadline)

Bring this up after the slot-array version to kill the O(n·maxDeadline) worst case — phrase it as 'union-find as a next-free-slot pointer'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The slow part of the slot-array version is the backward scan for a free slot. Could you jump straight to the latest free slot ≤ d in almost O(1)?

2Hint 2Explore hint

Use a disjoint-set structure where parent[t] points to the latest free slot at or before t. find(d) returns it directly.

3Hint 3Explore hint

After assigning slot t, union it to t−1 so future finds skip past the now-occupied slot. Path compression makes this near-constant amortised.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

jobs by profit: (d3,20),(d1,40),(d1,30),(d1,10)

Array state

init

parent[t] = t

slot0 ↓

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final resultcount = 2, profit = 60

C · Code with teaching comments

solution.javaJava

Profit Sort + Union-Find Slot Lookup (Optimal) — optimal

5 teaching notes

1
private int[] parent;
2
 
3
private int find(int x) {
4
    if (parent[x] != x) parent[x] = find(parent[x]); // path compression
5
    return parent[x];
6
}
7
 
8
public int[] jobScheduling(int[] deadline, int[] profit) {
9
    int n = deadline.length;
10
    Integer[] idx = new Integer[n];
11
    for (int i = 0; i < n; i++) idx[i] = i;
12
    Arrays.sort(idx, (a, b) -> Integer.compare(profit[b], profit[a])); // profit desc
13
    int maxD = 0;
14
    for (int d : deadline) maxD = Math.max(maxD, d);
15
    parent = new int[maxD + 1];
16
    for (int t = 0; t <= maxD; t++) parent[t] = t; // slot 0 = sentinel
17
    int count = 0;
18
    long totalProfit = 0;
19
    for (int i = 0; i < n; i++) {
20
        int j = idx[i];
21
        // Jump straight to the latest free slot ≤ the job's deadline.
22
        int slot = find(Math.min(maxD, deadline[j]));
23
        if (slot > 0) {
24
            parent[slot] = slot - 1; // mark used, forward to previous free
25
            count++;
26
            // Long accumulator to avoid overflow on summed profits.
27
            totalProfit += profit[j];
28
        }
29
    }
30
    return new int[]{count, (int) Math.min(totalProfit, Integer.MAX_VALUE)};
31
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.31 lines

D · Why it works and complexityO(n log n + n·α(n)) timeO(maxDeadline) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7all deadline = 1 — find(1) succeeds once, then parent[1]=0 → every later job finds slot 0 and is dropped.Explore edge cases

Edge cases handled

all deadline = 1find(1) succeeds once, then parent[1]=0 → every later job finds slot 0 and is dropped.
deadlines distinct & ampleEach find hits a fresh slot → all jobs scheduled.
duplicate max profitsTie order doesn't affect total profit; both get distinct slots if available.

Pitfalls

Forgetting the slot-0 sentinel — find could return an invalid slot and you'd schedule a job nowhere.
Skipping path compression — finds degrade toward O(maxDeadline) and you lose the speed-up.
Unioning to slot+1 instead of slot−1 — you must forward to the EARLIER free slot, not later.
Capping deadline incorrectly — clamp to maxDeadline so find stays in bounds.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewprivate int[] parent; private int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); // path compression return parent[x];Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Earliest-slot instead of latest-slot placement

Explore the code comparison

Don't write this

for (int t = 1; t <= Math.min(maxD, deadline[j]); t++) {
    if (!slot[t]) { slot[t] = true; break; }   // earliest free — WRONG
}

Write this instead

for (int t = Math.min(maxD, deadline[j]); t >= 1; t--) {
    if (!slot[t]) { slot[t] = true; break; }   // latest free — correct
}

Sorting by deadline rather than profit

Deadline order can place a low-profit job into a slot a high-profit job needed, reducing total profit. Profit-descending order guarantees any forced drop is the least valuable job.

Explore the code comparison

Don't write this

Arrays.sort(idx, (a, b) -> Integer.compare(deadline[a], deadline[b]));

Write this instead

Arrays.sort(idx, (a, b) -> Integer.compare(profit[b], profit[a]));

Profit accumulated in int

With up to 10⁵ jobs at 10⁹ profit each, the total reaches ~10¹⁴ and overflows a 32-bit int silently. Use a long (Java) — Python ints are unbounded.

Explore the code comparison

Don't write this

int totalProfit = 0;
totalProfit += profit[j];   // overflows

Write this instead

long totalProfit = 0;
totalProfit += profit[j];   // safe

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort by profit desc, place each job in the latest free slot ≤ its deadline

Code pattern to memorize

sort jobs by profit desc
slot[1..maxDeadline] = free
for job in jobs:
    for t from min(maxDeadline, job.deadline) down to 1:
        if slot[t] free: assign job to t; break
# union-find: find(d) returns latest free slot <= d in near-O(1)

Rules to remember

1Process jobs by profit descending — commit to the most valuable jobs first.
2Place each job as late as possible (latest free slot ≤ deadline), never early — this preserves earlier slots for jobs with tighter deadlines.
3Jobs are unit time: each occupies exactly one integer slot, so feasibility is purely 'is there a free slot ≤ deadline?'.
4Slots are 1-indexed up to maxDeadline; a job with deadline d can use any of slots 1..d.
5For speed, replace the inner backward scan with union-find where find(d) jumps straight to the latest free slot ≤ d, then unions it to d−1.

Use this pattern when

Unit-time jobs, each with a deadline and a profit; maximise total profit of on-time jobs
A single machine processing one job per time unit
You can drop jobs entirely (no partial credit) and order is free within deadlines
Classic 'sort by value, fit greedily into latest slot' scheduling

Choose another pattern when

Jobs have arbitrary (non-unit) durations → this greedy breaks; use DP / flow
You must run every job (no dropping) → feasibility/ordering problem, not selection
Objective is minimise lateness / weighted completion time → different scheduling theory
Multiple machines in parallel → load-balancing, not single-slot greedy

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Course Schedule III
Coming soon
Variable durations with deadlines → greedy by deadline + a max-heap to evict the longest course.
Weighted Job Scheduling (variable length)
Coming soon
Non-unit durations break this greedy; sort by finish and DP with binary search instead.
Maximize Profit with K Machines
Coming soon
K parallel slots per time unit — generalise the slot/union-find capacity per timestamp.
Activity Selection
The unweighted sibling — maximise count of compatible intervals via finish-time greedy.

Same pattern

←

Activity Selection

Continue · Next problem

Connect N Ropes with Minimum Cost