Practice › Greedy
Job Sequencing
Medium · Greedy · Asked at Amazon, Microsoft, Flipkart, Accenture
Each job takes one unit of time and has a deadline and a profit; you earn the profit only if the job finishes by its deadline. Only one job runs at a time, starting at time 0. Print the maximum number of jobs done and the maximum total profit — the count is the number of jobs in a schedule with maximum profit (choose the schedule greedily by profit).
Input
First line: n. Next n lines: deadline profit.
Output
Two integers: the number of jobs done and the total profit.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ deadline ≤ n
- 1 ≤ profit ≤ 500
Sort jobs by profit (highest first). Put each job in the latest free time slot not after its deadline; skip it if none is free. A DSU over slots makes finding the slot fast.
Example 1
Input
4 4 20 1 10 1 40 1 30
Output
2 60
Example 2
Input
5 2 100 1 19 2 27 1 25 1 15
Output
2 127
Hints
- Consider the most profitable jobs first.
- Schedule each job as late as possible (the latest free slot ≤ its deadline), which keeps earlier slots free for jobs with earlier deadlines.
Approach
Sort jobs by profit descending. For each job, look for a free slot t from its deadline down to 1; if found, occupy it and add the profit. A union–find over slots (find(t) = latest free slot ≤ t, and occupying t links it to t − 1) turns the search into near O(1), giving O(n log n) overall.
Complexity: O(n log n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
vector<int> par;
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
int main() {
int n;
cin >> n;
vector<pair<int, int>> jobs(n); // (profit, deadline)
for (auto &j : jobs) cin >> j.second >> j.first;
sort(jobs.rbegin(), jobs.rend());
par.resize(n + 1);
iota(par.begin(), par.end(), 0);
long long count = 0, profit = 0;
for (auto &j : jobs) {
int slot = find(min(j.second, n));
if (slot > 0) {
par[slot] = slot - 1;
count++;
profit += j.first;
}
}
cout << count << " " << profit << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
jobs = sorted(((data[2 + 2 * i], data[1 + 2 * i]) for i in range(n)), reverse=True)
par = list(range(n + 1))
def find(x):
while par[x] != x:
par[x] = par[par[x]]
x = par[x]
return x
count = profit = 0
for p, d in jobs:
slot = find(min(d, n))
if slot > 0:
par[slot] = slot - 1
count += 1
profit += p
print(count, profit)Java solution
import java.util.*;
public class Main {
static int[] par;
static int find(int x) {
while (par[x] != x) {
par[x] = par[par[x]];
x = par[x];
}
return x;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] jobs = new int[n][2];
for (int i = 0; i < n; i++) {
jobs[i][1] = sc.nextInt();
jobs[i][0] = sc.nextInt();
}
Arrays.sort(jobs, (a, b) -> b[0] - a[0]);
par = new int[n + 1];
for (int i = 0; i <= n; i++) par[i] = i;
long count = 0, profit = 0;
for (int[] j : jobs) {
int slot = find(Math.min(j[1], n));
if (slot > 0) {
par[slot] = slot - 1;
count++;
profit += j[0];
}
}
System.out.println(count + " " + profit);
}
}