n one-off gigs. Gig i runs from starts[i] to ends[i] and pays pays[i].
Only one gig can be worked on at a time. If a gig ends at moment x, the next one may start exactly at x.
Choose a set of gigs with no overlapping time that earns the most in total, and return that total.starts=[1, 4, 2, 6], ends=[4, 6, 7, 9], pays=[30, 20, 60, 25] → 75
The chain 1–4, 4–6, 6–9 has no overlaps and earns 30 + 20 + 25 = 75. The best-paid gig 2–7 (60) overlaps all the others, so with it you cannot get more than 60.
starts=[1, 1, 1], ends=[5, 3, 2], pays=[8, 9, 4] → 9
All gigs start at time 1 and overlap, so only one can be taken: the best pays 9.
starts=[3, 5], ends=[5, 8], pays=[10, 12] → 22
The first ends at 5 and the second starts at 5 — that is not an overlap, so both fit: 22.
n = starts.length = ends.length = pays.length ≤ 5 · 10⁴starts[i] < ends[i] ≤ 10⁹pays[i] ≤ 10⁴starts=[1, 4, 2, 6], ends=[4, 6, 7, 9], pays=[30, 20, 60, 25]
75
Run checks the first 3 tests in your browser. Submit checks all 84 tests on the server, hidden ones included.