A climbing gym logs three kinds of half-open time interval [s, e) (in progress at minutes
s, s + 1, ..., e - 1):
climbs: one climber is on the wall;belayers: one staff member is on duty;inspections: the wall is under inspection.
Each staff member on duty can supervise at most per_staff climbers. A minute is unsafe when
at least one climber is on the wall and either an inspection is in progress or there are more
climbers than per_staff times the number of staff on duty.
Return [total, stretches]: the total number of unsafe minutes, and the number of maximal runs of
consecutive unsafe minutes (two runs separated by no safe minute count as one).
Examples
Input: climbs = [[0, 10], [2, 6], [4, 8]], belayers = [[0, 5], [7, 12]],
inspections = [[9, 11]], per_staff = 2
Output: [4, 2]
Explanation: Minute 4 has 3 climbers and 1 staff; minutes 5 and 6 have climbers and no staff;
minute 9 has a climber during an inspection. Unsafe minutes 4, 5, 6 and 9 form two runs.
Input: climbs = [[3, 8]], belayers = [], inspections = [], per_staff = 5
Output: [5, 1]
Constraints
- Each list has at most
3 * 10**4intervals;0 <= s < e <= 10**9;1 <= per_staff <= 100. - Intervals of the same kind may overlap or repeat.
- Target complexity: O(n log n) for n intervals in total. Recounting every interval for each stretch of time is far too slow for the largest tests.
Goals
- Sweep several kinds of interval at once, each with its own counter
- Apply all changes at one moment before judging the stretch that follows it
- Merge adjacent unsafe stretches into maximal runs