Order Batching

Problem: Order Batching DoorDash wants to combine food delivery orders into batches so that a Dasher can handle multiple orders together. You are given n orders. Each order has: order_id: a unique string without spaces; merchant_id: a string without spaces; ready_time: an integer representing the estimated pickup-ready time in minutes. You are also given two integers: k: the maximum number of orders allowed in one batch; w: within one batch, the difference between the latest and earliest ready_time must be at most w. A valid batch must satisfy all of the following: All orders in the batch come from the same merchant_id. The batch contains at most k orders. The maximum ready_time minus the minimum ready_time in the batch is at most w. Every order must appear in exactly one batch. Partition all orders into valid batches while minimizing the total number of batches. If multiple optimal answers exist, output the deterministic one produced by these rules: Process merchants in lexicographical order of merchant_id. For each merchant, sort its orders by (ready_time, order_id) ascending. Starting from the earliest unassigned order, greedily add as many following orders as possible until either the batch size reaches k or adding the next order would violate the time window w. Input Format n k w order_id_1 merchant_id_1 ready_time_1 order_id_2 merchant_id_2 ready_time_2 ... order_id_n merchant_id_n ready_time_n Output Format Print the number of batches m on the first line. Then print m lines. Each line contains the order_ids in one batch, separated by a single space. The order of batches follows the deterministic rules above. Constraints 1 <= n <= 2 * 10^5 1 <= k <= 10^5 0 <= w <= 10^9 0 <= ready_time <= 10^9 order_id is globally unique merchant_id and order_id contain only letters, digits, underscores, or hyphens Example Example 1 Input: 5 2 10 o1 m1 0 o2 m1 5 o3 m1 20 o4 m2 3 o5 m2 8 Output: 3 o1 o2 o3 o4 o5 Example Input 5 2 10 o1 m1 0 o2 m1 5 o3 m1 20 o4 m2 3 o5 m2 8 Output 3 o1 o2 o3 o4 o5