Each job takes one hour and pays only if finished by its deadline. Choose which jobs to do.
What to build
A greedy program that earns the most from jobs that each need one time slot.
Requirements
- Sort the jobs by profit, from highest to lowest.
- For each job, use the latest free slot at or before its deadline, and skip the job if there is none.
- Print how many jobs were done and the total profit.
Input
The first line has n. Each of the next n lines has a deadline and a profit.
Output
One line: the number of jobs done and the total profit.
Constraints
1 ≤ n ≤ 100, 1 ≤ deadline ≤ 100 and 1 ≤ profit ≤ 1000.
Example
Input:
4
4 20
1 10
1 40
1 30
Output:
2 60
Why it works
Taking the most profitable job first is safe, because any schedule without it can swap it in for a less profitable job. Using the latest free slot leaves the early slots for jobs that need them.
Examples
Example 1 · Input
4 4 20 1 10 1 40 1 30
Expected output
2 60
Example 2 · Input
5 2 100 1 19 2 27 1 25 3 15
Expected output
3 142
Hints
Hint 1
Sort the jobs by profit, largest first.
Hint 2
Give each job the latest free time slot that is not after its deadline. That keeps earlier slots free for jobs with tight deadlines.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n, deadline[100], profit[100];
int taken[101] = {0};
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d %d", &deadline[i], &profit[i]);
for (int i = 1; i < n; i++) {
int d = deadline[i], p = profit[i], j = i - 1;
while (j >= 0 && profit[j] < p) {
deadline[j + 1] = deadline[j];
profit[j + 1] = profit[j];
j--;
}
deadline[j + 1] = d;
profit[j + 1] = p;
}
int done = 0, total = 0;
for (int i = 0; i < n; i++) {
for (int slot = deadline[i]; slot >= 1; slot--) {
if (!taken[slot]) {
taken[slot] = 1;
done++;
total += profit[i];
break;
}
}
}
printf("%d %d\n", done, total);
return 0;
}