Frontend School

Swiggy Delivery Hub Optimization

DSA
medium

Swiggy Delivery Hub Optimization

Medium
Queue
Priority Queue
Simulation
System Design

Overview

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.

What you need to do / Task

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:

  1. Order Arrival & Preparation: Each order O arrives at O.arrivalTime and immediately begins preparation, which takes O.prepTime. An order is ready for delivery at O.arrivalTime + O.prepTime.
  2. Ready-to-Dispatch Queue: Once an order completes preparation, it enters a 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).
  3. Agent Assignment: There are 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.
  4. Delivery: Once an agent picks up an order, they become busy for O.deliveryTime. After O.deliveryTime, the agent becomes free again.

Your function should return the time when the very last order is successfully delivered.

Input & output

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 in the input 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.

Clarifications

  • Empty input: If orders is empty, the function should return 0.
  • Simultaneous events: If multiple events occur at the same time (e.g., an order finishes prep and an agent becomes free), prioritize processing orders that are ready for dispatch and assigning them to agents. The simulation should ensure all events up to currentTime are fully processed before advancing currentTime.
  • Data Structures: You may assume the availability of a 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

1

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.

2

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.

3

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

Constraints & assumptions

  • 1 <= orders.length <= 10^5
  • 0 <= arrivalTime, prepTime <= 10^9
  • 1 <= deliveryTime <= 10^9
  • 1 <= K <= 10^5
  • orders are sorted by arrivalTime in non-decreasing order.
  • All time values are non-negative integers.

Out of scope

  • Optimizing agent routes or considering geographical locations.
  • Handling agent breaks or dynamic agent availability changes.
  • Complex error handling or logging.

What interviewers evaluate

  • Correctness: The solution accurately simulates the order processing and calculates the final delivery time.
  • Algorithm Design: Effective use of appropriate data structures (queues, priority queues) to manage events and states.
  • Time & Space Complexity: An efficient solution that scales well with large inputs (e.g., O(N log N) or O(N log K)).
  • Code Structure & Readability: Clean, well-organized, and easy-to-understand code.

Loading editor...