Greedy / SchedulingJob SequencingMedium

Job Sequencing — Maximize Profit with Deadlines

Sort jobs by profit descending. For each job, assign it to the latest available slot before its deadline.

GFG
Practice on GeeksforGeeks: Job Sequencing Problem
Open Problem

Greedy Choice

Sort by profit descending. For each job, find the latest available time slot ≤ its deadline. This maximizes total profit by prioritizing high-value jobs.

Algorithm

sort jobs by profit DESC
for each job:
  for slot = deadline down to 1:
    if slot is free:
      assign job, break
// Max profit = sum of scheduled jobs
Interactive Visualization
Trying Slot
Scheduled
Skipped
Jobs (sorted by profit ↓)
Time Slots
Step 0 of 0
Total Profit
0
Scheduled
0
Current Job
—
Slots
0
Ready. Press Play or Next to start.
✓ Done
Speed
C++ — Job Sequencing
pair<int,int> jobSequencing(vector<tuple<int,int,int>>& jobs) {
    // jobs: {id, deadline, profit}
    sort(jobs.begin(), jobs.end(),
         [](auto& a, auto& b){ return get<2>(a) > get<2>(b); });

    int maxD = 0;
    for (auto& j : jobs) maxD = max(maxD, get<1>(j));

    vector<int> slot(maxD + 1, -1);
    int profit = 0, count = 0;

    for (auto& [id, dl, p] : jobs) {
        for (int s = dl; s >= 1; s--) {
            if (slot[s] == -1) {
                slot[s] = id;
                profit += p;
                count++;
                break;
            }
        }
    }
    return {count, profit};
}
Complexity
Time
O(N × D)

N jobs, D max deadline. Can optimize to O(N log N) with DSU.

Space
O(D)

Slot array of size max deadline.

📝 Notes

▼