Minimum Batches Within a Time Window
Problem statement
You are given event times in times. Put every event into exactly one batch and return the smallest number of batches.
- A batch contains at most
capacityevents. - If its earliest event is at time
t, every event in that batch must be at mostt + window.
For this exercise, times may arrive in any order. Events with the same time are separate events, and a time exactly at the window boundary is allowed. An empty input needs zero batches.
Function
minimumBatches(times: int[], capacity: int, window: int) → intExamples
Example 1
times = [1,3,5]capacity = 2window = 2return = 2Put times 1 and 3 together, then time 5 in a second batch. One batch cannot hold all three events.
Example 2
times = [7,1,1,2,8]capacity = 3window = 1return = 2After sorting, one batch holds 1, 1, 2 and the other holds 7, 8. Both batches stay within a window of 1.
Example 3
times = []capacity = 4window = 0return = 0There are no events to assign.
Constraints
- 0 <= times.length <= 100000
- 0 <= times[i] <= 10^9
- 1 <= capacity <= 100000
- 0 <= window <= 10^9