Skip to the code
cf.
+50 XP

#686 Booking Load With Range Adds

hard

A video-call scheduler tracks how many calls run in each of n time slots, numbered 0 to n - 1, all starting at 0. Booking a call adds to a whole range of slots, and the planner often asks for the busiest slot in a range. Write a class SlotLoad:

  • new SlotLoad(n) creates n empty slots.
  • add(left, right, amount) adds amount to every slot from left to right, inclusive. amount can be negative when calls are cancelled.
  • maxLoad(left, right) returns the largest load among slots left to right.

Both methods must take O(log n) time, even when the range covers almost every slot.

Each example lists the calls in order, then each call's arguments. The first call creates the object with new SlotLoad(…); the output lists what each call returns (null for the constructor and for methods that return nothing).

Example 1

Input: ["SlotLoad","add","add","maxLoad","maxLoad","maxLoad"]
[[6],[0,3,1],[2,5,2],[0,5],[0,1],[4,5]]
Output: [null,null,null,3,1,2]

Slots 2 and 3 get both bookings, 1 + 2 = 3. Slots 0 and 1 have 1, and slots 4 and 5 have 2.

Example 2

Input: ["SlotLoad","maxLoad"]
[[3],[0,2]]
Output: [null,0]

Nothing is booked, so every slot is 0.

Constraints

  • 1 <= n <= 10^5
  • 0 <= left <= right < n
  • -1000 <= amount <= 1000
  • At most 10^5 calls.
Saved in this browser

Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.

Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).