Job Sequencing with Deadlines

Each job takes unit time, has a deadline $d_j$ and a profit $p_j$. One machine. Maximise the total profit of jobs completed by their deadlines.

Greedy — sort by profit, schedule as late as possible

long long jobSequencing(vector<pair<long long,int>> jobs) {   // (profit, deadline)
    sort(jobs.rbegin(), jobs.rend());                          // profit descending
    int maxD = 0;
    for (auto& [p, d] : jobs) maxD = max(maxD, d);
 
    vector<bool> slot(maxD + 1, false);
    long long total = 0;
    for (auto& [p, d] : jobs)
        for (int t = min(d, maxD); t >= 1; t--)
            if (!slot[t]) { slot[t] = true; total += p; break; }
    return total;
}

$O(n\cdot d)$ naively. Scheduling each job as late as its deadline allows keeps the early slots free for jobs with tighter deadlines.

Speeding up the slot search

DSU as a “next free slot” pointer — $O(n\alpha )$

vector<int> par(maxD + 2);
iota(par.begin(), par.end(), 0);
function<int(int)> find = [&](int x) { return par[x] == x ? x : par[x] = find(par[x]); };
 
for (auto& [p, d] : jobs) {
    int t = find(min(d, maxD));
    if (t > 0) { total += p; par[t] = t - 1; }                 // slot t is now taken
}

par[t] points to the latest free slot at or before $t$. This is the DSU “next free slot” idiom, and it is the standard way to make this greedy near-linear.

Min-heap — $O(n\log n)$

Sort by deadline ascending; keep a min-heap of the chosen profits. Add each job; if the count exceeds its deadline, drop the smallest profit so far.

sort(jobs.begin(), jobs.end(), byDeadline);
priority_queue<long long, vector<long long>, greater<>> pq;
for (auto& [d, p] : jobs) {
    pq.push(p);
    if ((int)pq.size() > d) pq.pop();                          // drop the least valuable
}
long long total = 0;
while (!pq.empty()) { total += pq.top(); pq.pop(); }

Elegant and easy to remember: “take everything, then discard the worst whenever you exceed capacity” — a pattern that recurs whenever a greedy must undo a past choice.

Why greedy is optimal

The feasible sets of jobs (those schedulable within their deadlines) form a transversal matroid. Greedy by weight is optimal on any matroid, so no exchange argument is even needed — see Exchange Arguments.

Concretely: a set $S$ is feasible iff for every $t$, at most $t$ jobs in $S$ have deadline $\le t$ (Hall’s condition).

Variants

Variant	Method
Unit jobs, maximise profit	this page
Unit jobs, maximise count	same with equal profits
Arbitrary processing times, minimise late jobs	Moore-Hodgson, $O(n\log n)$
Arbitrary times, minimise max lateness	EDD
With precedence constraints	Lawler, $O(n^2)$
With release times	NP-hard
Multiple machines	greedy with $m$ slots per time unit, or flow
Deadlines and durations, maximise profit	DP — NP-hard in general

Moore-Hodgson — minimise the number of late jobs

Jobs have arbitrary durations $p_j$ and deadlines $d_j$; minimise how many finish late.

sort(jobs.begin(), jobs.end(), byDeadline);
priority_queue<long long> pq;                                  // max-heap of durations
long long t = 0;
for (auto& [d, p] : jobs) {
    t += p; pq.push(p);
    if (t > d) { t -= pq.top(); pq.pop(); }                    // drop the longest job
}
// pq.size() jobs are on time; n - pq.size() are late

The same “take then discard the worst” shape as above — dropping the longest job whenever the schedule becomes infeasible. $O(n\log n)$, and provably optimal.

The reusable pattern

Process items in a natural order, greedily accept everything, and when a constraint is violated, discard the least useful item accepted so far.

A max-heap (or min-heap) makes the discard $O(\log n)$. This solves:

• job sequencing (drop the smallest profit),
• Moore-Hodgson (drop the longest job),
• “maximum items within a budget” (drop the most expensive),
• “attend the maximum number of events” (drop the latest-ending),
• IPO / capital problems (a heap of affordable projects).

Recognising it converts a family of scheduling problems into ten lines each.

See also: Minimising Maximum Lateness · DSU · Exchange Arguments