Frontend School

Swiggy Order Dispatch Optimization

DSA
medium

Swiggy Order Dispatch Optimization

Medium
Heap
Priority Queue
Greedy

Overview

At Swiggy, efficient order dispatch is crucial for customer satisfaction and operational excellence. Delivery executives need to pick up orders from restaurants, but not all orders are ready at the same time, and some orders are more critical than others. This problem simulates a core part of our dispatch system, focusing on how we prioritize and assign orders based on their readiness and importance.

What you need to do / Task

Implement a function dispatchOrders that simulates the dispatch of k orders to delivery executives. The system should prioritize orders based on the following rules:

  1. Highest Priority Score First: Orders with a higher priorityScore are dispatched first.
  2. Earliest Preparation Time First: If two or more orders have the same priorityScore, the one that became ready earliest (i.e., has a lower preparationTime) is dispatched first.
  3. Lexicographical Order ID: If priorityScore and preparationTime are identical for multiple orders, the order with the lexicographically smallest orderId is dispatched first.

You need to return the orderIds of the k dispatched orders, in the order they are dispatched.

Input & output

Function Signature: function dispatchOrders(orders: [string, number, number][], k: number): string[]

Parameters:

  • orders: An array of orders. Each order is a tuple [orderId: string, preparationTime: number, priorityScore: number].
    • orderId: A unique string identifier for the order.
    • preparationTime: An integer representing the time (in minutes from an arbitrary start) when the order will be ready for pickup. An order cannot be dispatched before this time.
    • priorityScore: An integer representing the priority of the order. Higher values indicate higher priority.
  • k: An integer representing the number of orders to dispatch.

Return Value:

  • An array of strings, containing the orderIds of the k dispatched orders, in the order of their dispatch. If fewer than k orders can be dispatched, return all available orders.

Clarifications

  • The simulation starts at time 0. Delivery executives are assumed to be available to pick up orders instantly. The currentTime only advances if there are no ready orders and the system must wait for the next order to become available.
  • If k is greater than the total number of orders, dispatch all available orders following the prioritization rules.
  • If the orders array is empty, return an empty array.
  • All orderIds are unique.

Examples

1

Example 1

Input:

orders = [["O1", 0, 5], ["O2", 2, 8], ["O3", 1, 5], ["O4", 0, 10]], k = 3

Output:

["O4","O1","O3"]

Note:

Initial currentTime = 0.

  1. At t=0, O1(0,5) and O4(0,10) are ready. O4 is chosen (priority 10 > 5).
  2. At t=0, O1(0,5) is the only ready order. O1 is chosen.
  3. At t=0, no orders are ready. Advance currentTime to 1 (O3's prep time). At t=1, O3(1,5) is ready. O3 is chosen.
2

Example 2

Input:

orders = [["A", 5, 10], ["B", 5, 10], ["C", 5, 9]], k = 2

Output:

["A","B"]

Note:

All orders are ready at t=5.

  1. A(5,10) and B(5,10) have highest priority. A is chosen over B due to lexicographically smaller orderId.
  2. B(5,10) is the next best available. B is chosen.
3

Example 3

Input:

orders = [["X", 10, 7], ["Y", 12, 9], ["Z", 8, 6]], k = 1

Output:

["Z"]

Note:

Initial currentTime = 0. No orders are ready. Advance currentTime to 8 (Z's prep time).

  1. At t=8, Z(8,6) is ready. Z is chosen. X and Y are not yet ready.

Constraints

Constraints & assumptions

  • 1 <= orders.length <= 10^5 (denoted as N)
  • 1 <= k <= N
  • orderId length: 1 <= |orderId| <= 10
  • 0 <= preparationTime <= 10^9
  • 1 <= priorityScore <= 1000
  • Time complexity target: O(N log N) or O(K log N)
  • Space complexity target: O(N)

What interviewers evaluate

  • Correct application of priority queue (heap) data structures for managing orders.
  • Accurate implementation of the complex tie-breaking logic across multiple criteria (priorityScore, preparationTime, orderId).
  • Efficiently handling the advancement of currentTime to ensure orders are only dispatched when ready.
  • Robustness in handling edge cases, such as an empty orders list or k exceeding the total number of orders.

Loading editor...