Swiggy Delivery Hub Optimization
Swiggy's delivery hubs are critical for ensuring timely food delivery. Orders arrive, undergo preparation, and then await dispatch by an available delivery agent. Efficiently managing this process is key to minimizing customer wait times and optimizing operational costs. This problem simulates a simplified order dispatch system to determine the total time required to process all orders from arrival to final delivery.
You are tasked with implementing a function that calculates the total time until all orders are delivered, given a list of orders and the number of available delivery agents. Your solution must accurately simulate the following process:
O arrives at O.arrivalTime and immediately begins preparation, which takes O.prepTime. An order is ready for delivery at O.arrivalTime + O.prepTime.Ready-to-Dispatch Queue. Orders are added to this queue based on their preparation completion time. If multiple orders complete preparation at the same time, they are added to the queue in the order they were provided in the input array (maintaining original relative order).K delivery agents. An agent can only pick up an order if they are free. Agents pick orders from the Ready-to-Dispatch Queue on a First-In, First-Out (FIFO) basis. If multiple agents are free, any free agent can pick up the next ready order. If no agents are free, orders wait in the Ready-to-Dispatch Queue.O.deliveryTime. After O.deliveryTime, the agent becomes free again.Your function should return the time when the very last order is successfully delivered.
Function Signature:
function calculateTotalDeliveryTime(orders: number[][], K: number): number
orders: An array of arrays, where each inner array [arrivalTime, prepTime, deliveryTime] represents an order.
arrivalTime: The time (non-negative integer) when the order is placed at the hub.prepTime: The time (non-negative integer) it takes to prepare the order.deliveryTime: The time (positive integer) it takes to deliver the order once an agent picks it up.orders array are guaranteed to be sorted by arrivalTime in non-decreasing order.K: A positive integer representing the number of available delivery agents.
Returns: A single non-negative integer representing the total time elapsed until the last order is delivered.
orders is empty, the function should return 0.currentTime are fully processed before advancing currentTime.MinPriorityQueue (min-heap) data structure with enqueue, dequeue, isEmpty, and front (peek) operations, or implement a basic version if time permits. For MinPriorityQueue<number>, the number itself is the priority. For MinPriorityQueue<[number, number, number]>, the first element of the tuple ([0]) is the primary priority, and the second ([1]) is the secondary tie-breaking priority.Examples
Example 1
Input:
orders = [[0, 2, 3], [1, 1, 2]], K = 1
Output:
7
Note:
Time 0: Order 1 ([0,2,3]) arrives. Prep starts. Agent 1 free. Time 1: Order 2 ([1,1,2]) arrives. Prep starts. Time 2: Order 1 (prep: 0+2=2) and Order 2 (prep: 1+1=2) both finish preparation. They enter Ready-to-Dispatch Queue in input order: [Order 1, Order 2]. Agent 1 is free. Agent 1 picks Order 1. Agent 1 busy until 2+3=5. Time 5: Agent 1 becomes free. Picks Order 2 from queue. Agent 1 busy until 5+2=7. Time 7: Agent 1 becomes free. All orders delivered. Total time = 7.
Example 2
Input:
orders = [[0, 1, 5], [0, 1, 5], [0, 1, 5]], K = 2
Output:
11
Note:
Time 0: Order 1, 2, 3 arrive. Prep starts for all. Agents 1 & 2 free. Time 1: Order 1, 2, 3 all finish preparation (0+1=1). Ready-to-Dispatch Queue: [O1, O2, O3]. Agent 1 picks O1. Busy until 1+5=6. Agent 2 picks O2. Busy until 1+5=6. Ready-to-Dispatch Queue: [O3]. Time 6: Agent 1 becomes free. Picks O3. Busy until 6+5=11. Agent 2 is free. Time 11: Agent 1 becomes free. All orders delivered. Total time = 11.
Example 3
Input:
orders = [[10, 5, 10], [12, 3, 7], [15, 2, 8]], K = 1
Output:
40
Note:
Time 0-9: Idle. Time 10: O1 arrives (index 0). Prep starts. Agent 1 free. Time 12: O2 arrives (index 1). Prep starts. Time 15: O3 arrives (index 2). Prep starts. At currentTime=15: O1 finishes prep (10+5=15). Add [15, 0, 10] to ordersInPreparation. O2 finishes prep (12+3=15). Add [15, 1, 7] to ordersInPreparation. ordersInPreparation: [[15,0,10], [15,1,7]]. Move from ordersInPreparation to Ready-to-Dispatch Queue: O1 (prep_end=15, index=0) ready. Ready-to-Dispatch Queue: [10]. O2 (prep_end=15, index=1) ready. Ready-to-Dispatch Queue: [10, 7]. Agent 1 is free (at time 0, updated to 15). Picks O1 (deliveryTime=10). Agent 1 busy until 15+10=25. Ready-to-Dispatch Queue: [7]. At currentTime=17 (next event: O3 prep finishes): O3 finishes prep (15+2=17). Add [17, 2, 8] to ordersInPreparation. ordersInPreparation: [[17,2,8]]. Move from ordersInPreparation to Ready-to-Dispatch Queue: O3 (prep_end=17, index=2) ready. Ready-to-Dispatch Queue: [7, 8]. At currentTime=25 (next event: Agent 1 free): Agent 1 becomes free. Picks O2 (deliveryTime=7). Agent 1 busy until 25+7=32. Ready-to-Dispatch Queue: [8]. At currentTime=32 (next event: Agent 1 free): Agent 1 becomes free. Picks O3 (deliveryTime=8). Agent 1 busy until 32+8=40. Ready-to-Dispatch Queue: []. At currentTime=40: Agent 1 becomes free. All orders delivered. Total time = 40.
Constraints
1 <= orders.length <= 10^50 <= arrivalTime, prepTime <= 10^91 <= deliveryTime <= 10^91 <= K <= 10^5orders are sorted by arrivalTime in non-decreasing order.O(N log N) or O(N log K)).Loading editor...