Job Sequencing with Deadlines
Job Sequencing with Deadlines maximizes total profit of unit-time jobs before their deadlines by sorting by profit descending and scheduling each job in its latest free slot using Union-Find.
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
Job Sequencing with Deadlines
Given $n$ unit-time jobs, each with a deadline ($1 \le d_i \le n$) and profit $p_i$, schedule at most one job per time slot to maximize total profit. Sorting jobs by profit descending and placing each job in the latest available slot $\le d_i$ is optimal—and using Union-Find (DSU) to jump straight to the latest free slot drops the runtime from $O(n^2)$ to $O(n \log n)$!
At a Glance
| Implementation | Time Complexity | Space |
| :--- | :---: | :---: |
| Greedy + Linear Slot Scan | $O(n \log n + n \cdot D)$ | $O(D)$ |
| Greedy + Union-Find (DSU) | $O(n \log n)$ | $O(D)$ |
---
Practice Problems
Intermediate
1. Job Sequencing in $O(n \log n)$ Using DSU
Return {jobsScheduled, maxProfit} for unit-time jobs with deadlines and profits.
Approach: find(d) returns the latest free slot $\le d$ (or 0 if none). When placing a job in slot s, union s with s - 1 (parent[s] = find(s - 1))! Time: $O(n \log n)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
struct Job { int id, deadline, profit; };
std::pair<int, int> jobSequencing(std::vector<Job> jobs) {
std::sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) { return a.profit > b.profit; });
int maxD = 0;
for (const auto& j : jobs) maxD = std::max(maxD, j.deadline);
std::vector<int> parent(maxD + 1);
std::iota(parent.begin(), parent.end(), 0);
auto findFree = [&](auto& self, int s) -> int {
return parent[s] == s ? s : parent[s] = self(self, parent[s]);
};
int count = 0, profit = 0;
for (const auto& j : jobs) {
int slot = findFree(findFree, std::min(j.deadline, maxD));
if (slot > 0) {
parent[slot] = findFree(findFree, slot - 1);
++count;
profit += j.profit;
}
}
return {count, profit};
}
int main() {
auto [cnt, prof] = jobSequencing({{1, 2, 100}, {2, 1, 19}, {3, 2, 27}, {4, 1, 25}, {5, 3, 15}});
std::cout << "Jobs=" << cnt << " Profit=" << prof << "\n"; // Jobs=3 Profit=142
return 0;
}
</details>
---
Related Algorithms
- Activity Selection — unweighted interval scheduling.
- Union-Find (DSU) — accelerates latest-free-slot lookup to $O(\alpha(n))$.