AntInLoop

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