A ground station builds a repeating daily plan for its antenna. The day has L minutes, numbered 0..L-1, and after minute L-1 comes minute 0 of the next day, which the plan also covers, because the same plan is used every day.
Each request bookings[i] = (s, k) asks for the k consecutive minutes s, s+1, ..., s+k-1, counted modulo L. So a request may run past midnight: with L = 24, the request (22, 4) uses minutes 22, 23, 0 and 1. Two requests conflict if they share at least one minute. Return the largest number of requests that can be accepted with no two in conflict.
Examples
Input: L = 24, bookings = [(22, 4), (3, 5), (9, 6), (15, 5)]
Output: 4
Explanation: minutes 22-1, 3-7, 9-14 and 15-19 never overlap.
Input: L = 10, bookings = [(0, 3), (3, 3), (6, 3), (8, 4)]
Output: 3
Explanation: (0, 3), (3, 3) and (6, 3) use minutes 0-2, 3-5 and 6-8.
(8, 4) uses minutes 8, 9, 0 and 1, so it conflicts with (0, 3) and (6, 3).
Constraints
1 <= L <= 10**90 <= len(bookings) <= 2 * 10**40 <= s < L,1 <= k <= L(a request withk = Lneeds the whole day)- Target complexity: O(n log n). Rerunning a full greedy pass once per request is too slow for the largest tests.
Goals
- Recognise why interval scheduling on a line does not carry over to a circle unchanged
- Reduce the circle to lines by fixing one chosen booking
- Speed up many greedy runs with jump pointers