A session musician is offered gigs, each written as (start, end, pay): the gig occupies the time from start up to (but not including) end, and pays pay. The musician can play only one gig at a time, although a gig may start exactly when another ends. Return the largest total pay from a set of gigs that do not overlap.
Examples
Input: gigs = [(1, 4, 5), (3, 6, 6), (4, 7, 4), (6, 9, 5)]
Output: 11
Explanation: play (3, 6, 6) then (6, 9, 5). Taking the two gigs that finish earliest only earns 9.
Input: gigs = [(0, 10, 7), (0, 5, 3), (5, 10, 3)]
Output: 7
Constraints
0 <= len(gigs) <= 10**50 <= start < end <= 10**9,1 <= pay <= 10**4- Target complexity: O(n log n) time; an O(n^2) table is too slow for the largest tests.
Goals
- Sort intervals by end time so every earlier choice is a prefix
- Find the last compatible interval with binary search
- See why greedy by count or by pay fails when intervals have weights