Minimum Batches Under Capacity and Time Window

Problem You are given event time points t1, t2, ..., tn (integers, not necessarily sorted). You need to pack all events into batches. Each batch must satisfy: Capacity constraint: each batch contains at most B events. Time window constraint: for a batch, let s be the earliest time in the batch. Every event time t in that batch must satisfy t <= s + W (i.e., all events lie within a window of length W starting at the earliest event). Compute the minimum number of batches needed to pack all events. Input (stdin) Line 1: three integers n B W Line 2: n integers: the event time points Output (stdout) Print one integer: the minimum number of batches Constraints 1 <= n <= 2*10^5 1 <= B <= 2*10^5 0 <= W <= 1e9 0 <= ti <= 1e9 Example Input: 5 2 2 1 3 5 6 7 Output: 3 Explanation: one optimal batching is (1,3), (5,6), (7). Example Input 5 2 2 1 3 5 6 7 Output 3