Log inSign up
mediumGeeksforGeeksNot Started

Job Sequencing Problem

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on GeeksforGeeks
Lesson

Problem Statement

Given N jobs where each job i is represented by (id, deadline, profit). Each job takes exactly 1 unit of time to complete and can only be scheduled before or on its deadline. Only one job can be executed at any time unit.

Return an array or pair containing: 1. The maximum number of jobs done. 2. The maximum total profit earned.

Example 1 · Example 1: Standard Four Jobs:

Input: Jobs = [(1, 4, 20), (2, 1, 10), (3, 1, 40), (4, 1, 30)]
Output: [2, 60]
Explanation: Sorted by profit: Job 3 (40, dl:1), Job 4 (30, dl:1), Job 1 (20, dl:4), Job 2 (10, dl:1).\n- Job 3 placed at slot 1. Profit = 40.\n- Job 4 deadline is 1, slot 1 occupied -> cannot schedule.\n- Job 1 placed at slot 4. Profit = 40 + 20 = 60.\n- Job 2 deadline is 1, slot 1 occupied -> cannot schedule.\nTotal jobs = 2, total profit = 60.

Constraints:

  • 1 <= N <= 105
  • 1 <= deadline <= 105
  • 1 <= profit <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Prove why greedy sorting by profit combined with latest-slot assignment is optimal.
  • Understand the slot allocation optimization using DSU path compression.
  • Implement all three approaches across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Jobs with unit duration, explicit deadlines, and varying profits.
  • Single machine / worker execution constraint.
  • Goal is to maximize total profit collected.

Algorithmic Decision Tree:

  • Always sort descending by profit.
  • Use DSU slot parent tracking when maxDeadline is up to 105 to avoid quadratic slowdown.

Connected Patterns:

Activity SelectionTask SchedulerCourse Schedule III

1. Backtracking Schedule Search

Intuition

Recursively try including and placing each job into available slots to evaluate all feasible subsets and maximize total profit.

Algorithm

  1. Step 1: Define a recursive backtracking function testing whether each job is included.
  2. Step 2: For each chosen subset, verify if a feasible deadline-compatible assignment of time slots exists.
  3. Step 3: Track and update the maximum profit achieved and corresponding job count.
  4. Step 4: Return the optimal count and profit.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Job {
8 int id, dead, profit;
9};
10
11class Solution {
12 int maxProfit = 0;
13 int maxJobs = 0;
14
15 void backtrack(int idx, const vector<Job>& jobs, vector<bool>& slotUsed, int currentProfit, int currentJobs) {
16 if (idx == jobs.size()) {
17 if (currentProfit > maxProfit) {
18 maxProfit = currentProfit;
19 maxJobs = currentJobs;
20 } else if (currentProfit == maxProfit) {
21 maxJobs = max(maxJobs, currentJobs);
22 }
23 return;
24 }
25
26 // Option 1: Do not pick current job
27 backtrack(idx + 1, jobs, slotUsed, currentProfit, currentJobs);
28
29 // Option 2: Try picking current job in any valid slot
30 for (int t = min((int)slotUsed.size() - 1, jobs[idx].dead); t >= 1; --t) {
31 if (!slotUsed[t]) {
32 slotUsed[t] = true;
33 backtrack(idx + 1, jobs, slotUsed, currentProfit + jobs[idx].profit, currentJobs + 1);
34 slotUsed[t] = false;
35 break; // Greedily latest slot is always preferred
36 }
37 }
38 }
39
40public:
41 vector<int> JobScheduling(Job arr[], int n) {
42 vector<Job> jobs(arr, arr + n);
43 int maxDead = 0;
44 for (int i = 0; i < n; ++i) maxDead = max(maxDead, arr[i].dead);
45
46 vector<bool> slotUsed(maxDead + 1, false);
47 maxProfit = 0;
48 maxJobs = 0;
49 backtrack(0, jobs, slotUsed, 0, 0);
50
51 return {maxJobs, maxProfit};
52 }
53};
54
55int main() {
56 Solution sol;
57 Job arr[] = {{1, 4, 20}, {2, 1, 10}, {3, 1, 40}, {4, 1, 30}};
58 int n = sizeof(arr) / sizeof(arr[0]);
59 vector<int> ans = sol.JobScheduling(arr, n);
60 cout << "Jobs Done: " << ans[0] << ", Max Profit: " << ans[1] << endl;
61 return 0;
62}

Time & Space Complexity

  • Time complexity: O(2^N)
  • Space complexity: O(N)

2. Greedy Sort + Linear Slot Search

Intuition

Sort jobs descending by profit. For each job, linearly search backward from its deadline to slot 1 for the first free slot.

Algorithm

  1. Step 1: Sort jobs descending by profit.
  2. Step 2: Find the maximum deadline across all jobs and initialize a boolean array slot[] of size maxDeadline + 1 to false.
  3. Step 3: For each job, iterate backward from min(maxDeadline, job.deadline) down to 1.
  4. Step 4: If an unoccupied slot is found, mark it occupied, add profit to total profit, increment jobs done, and break.
  5. Step 5: Return [count, totalProfit].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Job {
8 int id, dead, profit;
9};
10
11class Solution {
12public:
13 vector<int> JobScheduling(Job arr[], int n) {
14 vector<Job> jobs(arr, arr + n);
15 sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
16 return a.profit > b.profit;
17 });
18
19 int maxDead = 0;
20 for (int i = 0; i < n; ++i) maxDead = max(maxDead, jobs[i].dead);
21
22 vector<int> slot(maxDead + 1, -1);
23 int countJobs = 0, totalProfit = 0;
24
25 for (int i = 0; i < n; ++i) {
26 for (int j = jobs[i].dead; j > 0; --j) {
27 if (slot[j] == -1) {
28 slot[j] = jobs[i].id;
29 countJobs++;
30 totalProfit += jobs[i].profit;
31 break;
32 }
33 }
34 }
35
36 return {countJobs, totalProfit};
37 }
38};
39
40int main() {
41 Solution sol;
42 Job arr[] = {{1, 4, 20}, {2, 1, 10}, {3, 1, 40}, {4, 1, 30}};
43 int n = sizeof(arr) / sizeof(arr[0]);
44 vector<int> ans = sol.JobScheduling(arr, n);
45 cout << "Jobs Done: " << ans[0] << ", Max Profit: " << ans[1] << endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(N log N + N * M)
  • Space complexity: O(M) where M is max deadline

3. Greedy Sort + DSU Slot Allocation

Intuition

Sort jobs descending by profit. Use a Disjoint Set Union (DSU) structure to find the latest available slot in amortized nearly O(1) time.

Algorithm

  1. Step 1: Sort all jobs in descending order of profit.
  2. Step 2: Initialize DSU parent array of size maxDeadline + 1 where parent[i] = i for all 0 <= i <= maxDeadline.
  3. Step 3: Define find(t): returns the latest free slot available at or before t with path compression.
  4. Step 4: For each job, find available slot available = find(job.deadline).
  5. Step 5: If available > 0, assign job, add profit, increment count, and union parent[available] = find(available - 1).
  6. Step 6: Return [countJobs, totalProfit].

Interactive Trace for Job Sequencing

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Pick J1 (profit 100, deadline 2)
Visual state
Values and pointers at this exact step
pointers
S
empty
J1
empty
0
1
↑ placed
2
Check / comparison
Slot 2 is free.
Decision / next transition
Assign J1 to slot 2. Total profit = 100, count = 1.
Why this step matters

Step 1: Pick J1 (profit 100, deadline 2). Assign to latest free slot: slot 2.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Job {
8 int id, dead, profit;
9};
10
11class DSU {
12 vector<int> parent;
13public:
14 DSU(int n) {
15 parent.resize(n + 1);
16 for (int i = 0; i <= n; ++i) parent[i] = i;
17 }
18
19 int find(int i) {
20 if (parent[i] == i) return i;
21 return parent[i] = find(parent[i]);
22 }
23
24 void unionSets(int u, int v) {
25 parent[u] = v;
26 }
27};
28
29class Solution {
30public:
31 vector<int> JobScheduling(Job arr[], int n) {
32 vector<Job> jobs(arr, arr + n);
33 sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
34 return a.profit > b.profit;
35 });
36
37 int maxDead = 0;
38 for (int i = 0; i < n; ++i) maxDead = max(maxDead, jobs[i].dead);
39
40 DSU dsu(maxDead);
41 int countJobs = 0, totalProfit = 0;
42
43 for (int i = 0; i < n; ++i) {
44 int availableSlot = dsu.find(jobs[i].dead);
45 if (availableSlot > 0) {
46 countJobs++;
47 totalProfit += jobs[i].profit;
48 // Merge this slot with the slot before it
49 dsu.unionSets(availableSlot, dsu.find(availableSlot - 1));
50 }
51 }
52
53 return {countJobs, totalProfit};
54 }
55};
56
57int main() {
58 Solution sol;
59 Job arr[] = {{1, 4, 20}, {2, 1, 10}, {3, 1, 40}, {4, 1, 30}};
60 int n = sizeof(arr) / sizeof(arr[0]);
61 vector<int> ans = sol.JobScheduling(arr, n);
62 cout << "Jobs Done: " << ans[0] << ", Max Profit: " << ans[1] << endl;
63 return 0;
64}

Time & Space Complexity

  • Time complexity: O(N log N + N * α(M))
  • Space complexity: O(M) where M is max deadline

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Permutation Subset SearchO(N!)O(N)Generate all possible execution schedules across time slots and find the schedule yielding maximum total profit.Exponential permutations.
2.Better — Greedy Sort + Linear Slot ArrayO(N log N + N * M)O(M) where M is maximum deadlineSort jobs descending by profit. For each job, iterate backwards from its deadline down to slot 1 to find an unoccupied time slot.Repeated backward linear search for open slots.
3.Optimal — Greedy Sort + Disjoint Set Union (DSU)OptimalO(N log N + N * α(M))O(M)Initialize DSU where parent[t] points to the latest free slot available at or before time t. When a slot is used, union it with parent[t - 1] with path compression.Initial sorting by profit.
Back to DSA Sheet