1265. Skip One Booking
A conference centre has n rooms in a row, all starting with zero guests. The booking log ops holds entries [l, r, v]: the booking adds v guests to every room from index min(l, r) to max(l, r), inclusive. All values v are non-negative.
Exactly one booking must be cancelled, and every other booking stays. After the cancellation, the peak is the largest guest count in any single room. Return the smallest peak that can be reached by choosing which one booking to cancel, as a 64-bit integer.
Trying every cancellation with a fresh rebuild is too slow for 100,000 bookings. Aim for O((n + m) log n) time and O(n log n) space, where m is the number of bookings.
Example 1
- Input:
- n = 5, ops = [[0,2,3],[1,4,2],[3,3,5]]
- Output:
- 5
- Explanation:
Skipping [3, 3, 5] leaves the room counts 3, 5, 5, 2, 2 with peak 5, while skipping [0, 2, 3] leaves peak 7, so the smallest peak is 5.
Example 2
- Input:
- n = 1, ops = [[0,0,7]]
- Output:
- 0
- Explanation:
The only booking must be cancelled, leaving one empty room, so the answer is 0.
Example 3
- Input:
- n = 4, ops = [[3,1,4],[0,0,9],[2,2,1]]
- Output:
- 5
- Explanation:
The first entry covers rooms 1 to 3 even though l > r. Cancelling [0, 0, 9] leaves the room counts 0, 4, 5, 5, and any other cancellation leaves the 9, so the answer is 5.
Constraints
1 ≤ n ≤ 105
1 ≤ ops.length ≤ 105
0 ≤ l, r < n; 0 ≤ v ≤ 105
All values fit in a 64-bit integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,400 msC++ 600 msJava 1,200 msJavaScript 1,200 msTypeScript 1,200 ms
Expected complexity
- Time
- O((n + m) log n)
- Space
- O(n log n)