468. The Most Profitable Set of Jobs
Each job has a start time, an end time and a profit. Two jobs conflict if their
half-open intervals [start, end) overlap, so a job ending at t and a job starting
at t may both be taken. Choose any set of pairwise non-conflicting jobs and print
the largest total profit.
(1,3,50) (2,5,20) (4,6,70) (6,7,60) -> 180
The answer above takes jobs 1, 3 and 4. It skips job 2 even though job 2 is available at time 2.
Problem #457 asks for the LONGEST chain of non-overlapping pairs, and sorting by end time with a greedy solves it. That greedy is wrong here, and the reason is worth stating precisely: with profits, ending earliest is no longer the only thing that matters, because a job that ends later may be worth more than everything that fits after it.
(1,4,100) (2,3,50) (3,5,60) is the sample for that. The greedy takes (2,3,50)
first because it ends earliest, then (3,5,60), for 110. Here 110 happens to be
optimal, and that is the point: the greedy reaching the right total on one input does
not make it correct. (0,5,10) (1,2,4) (2,3,4) (3,4,4) answers 12 from the three
short jobs, and the greedy also finds it, while
(1,3,4) (3,5,4) (5,7,4) (1,7,11) -> 12
needs the three short jobs rather than the single fat one, so a greedy on PROFIT descending gets 11 and is wrong. No ordering alone decides this. You have to compare.
## The recurrence
Sort by end time. Then dp[i] is the best profit using only the first i jobs:
dp[0] = 0
dp[i] = max( dp[i-1], skip job i
profit[i] + dp[p(i)] ) take job i
where p(i) is the number of jobs whose end time is at most job i's start time.
Because the list is sorted by end, p(i) is found by binary search, and every job it
admits sits at a smaller index, so one forward pass fills the table.
The take branch is the whole content: taking job i forbids everything that overlaps
it, and since the list is sorted by end, "everything compatible" is exactly a PREFIX,
which is why a single number dp[p(i)] summarises it.
Profits reach 10^9 and there can be 2 * 10^5 jobs, so the total needs 64 bits.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ start < end ≤ 1000000000` - `1 ≤ profit ≤ 1000000000`
Input
The first line contains an integer n.
Each of the next n lines contains three integers: the start, the end and the profit of one job.
Output
Print the largest total profit achievable by a set of pairwise non-conflicting jobs.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.