gigs[i] = [start, end, pay] means the gig takes days start through end, inclusive, and pays pay.
Only one gig can be played at a time, and a gig that is taken must be played in full. The end day counts, so two gigs where one ends on the day the other begins cannot both be taken.
At most limit gigs may be taken (fewer is fine). Return the largest total pay.gigs=[[1, 3, 5], [4, 6, 3], [2, 5, 7], [7, 7, 2]], limit=2 → 9
The best choice is the gigs [2, 5] and [7, 7]: 7 + 2 = 9. The pair [1, 3] and [4, 6] only gives 8.
gigs=[[1, 3, 5], [4, 6, 3], [2, 5, 7], [7, 7, 2]], limit=3 → 10
Now three fit: [1, 3], [4, 6] and [7, 7], for 5 + 3 + 2 = 10.
gigs=[[1, 2, 3], [2, 4, 4]], limit=2 → 4
Both gigs use day 2, so only one can be taken, and the better-paid one wins.
gigs=[[1, 3, 5], [4, 6, 3], [2, 5, 7], [7, 7, 2]], limit=2
9
Run checks the first 3 tests in your browser. Submit checks all 105 tests on the server, hidden ones included.