Non-Overlapping Gigs
Each job has a start, an end, and a profit; you can only work one job at a time (a job ending at time t frees you for a job starting at t). Maximize total profit.
Input: the first line has N; each of the next N lines has start end profit.
Output: the maximum total profit.
Constraints:
- 1 ≤ N ≤ 105
- 0 ≤ start < end ≤ 109
- 1 ≤ profit ≤ 104
Sample Tests
Input 1
3 1 3 50 2 5 20 4 6 70
Output 1
120
Input 2
1 0 1 5
Output 2
5
Discussion (opens after you solve — no spoilers before)
No comments yet.