A venue receives booking requests [start, end, value]. Two bookings are compatible when one ends no later than the other starts (end <= start, so back-to-back bookings are fine). Choose a set of pairwise compatible bookings whose total value is as large as possible and return that total.
Examples
Input: bookings = [[1, 3, 5], [2, 5, 6], [4, 6, 5], [6, 7, 4]]
Output: 14
Explanation: [1,3] + [4,6] + [6,7] = 5 + 5 + 4 = 14.
Input: bookings = [[1, 4, 3], [2, 3, 4], [3, 5, 2]]
Output: 6
Explanation: [2,3] and [3,5] are back-to-back and together are worth 6.
Constraints
0 <= len(bookings) <= 10**50 <= start < end <= 10**9,1 <= value <= 10**6- Target complexity: O(n log n). Trying every subset is impossible.
Goals
- Sort bookings by end time to process them in a useful order
- Use binary search to find the last compatible booking
- Combine a sorted order with a prefix-best table