Frontend School

Swiggy: Multi-Drop Delivery Optimization

DSA
medium

Swiggy: Multi-Drop Delivery Optimization

Medium
Graph
Shortest Path
Dijkstra
Floyd-Warshall
Bitmask DP
State Space Search

Overview

Swiggy's success hinges on efficient delivery logistics. As a delivery agent, optimizing routes is crucial, especially when handling multiple orders simultaneously. This problem challenges you to find the fastest possible route for a single delivery agent tasked with picking up items from various restaurants and delivering them to their respective customers.

What you need to do / Task

Your task is to implement a function that calculates the minimum total time required for a delivery agent to complete all assigned orders. The agent starts at a given startLocation and must pick up each order's item from its pickupLocation before delivering it to its dropoffLocation. The agent can carry multiple items at once.

Specifically, you need to:

  1. Model the city's road network as a graph where locations are nodes and roads are edges with associated travel times.
  2. Given a set of orders, each with a pickupLocation and dropoffLocation.
  3. Determine the minimum total time for the agent to visit all pickupLocations (for items not yet picked up) and then all dropoffLocations (for items already picked up), ensuring each item is picked up before it's delivered.
  4. The agent can visit any location multiple times.

Input & output

Function Signature:

function findMinDeliveryTime(n: number, roads: number[][], startLocation: number, orders: number[][]): number
  • n: An integer representing the total number of locations in the city, indexed from 0 to n-1.
  • roads: A number[][] where each inner array [u, v, time] represents an undirected road between location u and location v that takes time minutes to travel. There might be multiple roads between the same pair of locations; the shortest one should be considered.
  • startLocation: An integer representing the agent's initial location.
  • orders: A number[][] where each inner array [pickupLocation, dropoffLocation] represents an order. pickupLocation is the restaurant and dropoffLocation is the customer's address. The agent must pick up the item at pickupLocation before delivering it to dropoffLocation.

Return Value:

  • An integer representing the minimum total time required to complete all deliveries. If it's impossible to complete all deliveries (e.g., no path exists to a required location), return -1. (However, for this problem, you can assume a path always exists between any two required locations).

Clarifications

  • All locations (nodes) are 0-indexed.
  • Roads are undirected. If a road [u, v, time] exists, you can travel from u to v or v to u in time minutes.
  • The agent can carry multiple picked-up orders simultaneously.
  • Picking up an item or dropping off an item at a location is considered an instantaneous action and does not add to the travel time.
  • The agent does not need to return to startLocation after completing all deliveries.

Examples

1

Example 1

Input:

n = 4, roads = [[0,1,10],[1,2,20],[2,3,10]], startLocation = 0, orders = [[1,3]]

Output:

40

Note:

Agent starts at 0. Path: 0 -> 1 (pickup order 0, time=10). At 1, item picked. Path: 1 -> 2 -> 3 (dropoff order 0, time=20+10=30). Total time = 10 + 30 = 40.

2

Example 2

Input:

n = 5, roads = [[0,1,10],[1,2,5],[2,3,10],[3,4,5],[0,4,30]], startLocation = 0, orders = [[1,3],[2,4]]

Output:

25

Note:

Agent starts at 0. APSP (shortest path between any two locations): 0 1 2 3 4 0: 0 10 15 25 20 1:10 0 5 15 10 2:15 5 0 10 5 3:25 15 10 0 5 4:20 10 5 5 0

Optimal path: 0 -> 1 (pickup order 0, time=10). State: (loc=1, p_mask=0b01, d_mask=0b00). Then 1 -> 2 (pickup order 1, time=5). State: (loc=2, p_mask=0b11, d_mask=0b00). Total time=15. Then 2 -> 4 (dropoff order 1, time=5). State: (loc=4, p_mask=0b11, d_mask=0b10). Total time=20. Then 4 -> 3 (dropoff order 0, time=5). State: (loc=3, p_mask=0b11, d_mask=0b11). Total time=25. All orders delivered in 25 minutes.

3

Example 3

Input:

n = 3, roads = [[0,1,5],[1,2,5]], startLocation = 0, orders = [[0,2]]

Output:

10

Note:

Agent starts at 0. At location 0, order 0 is picked up (instantaneous). State: (loc=0, p_mask=0b01, d_mask=0b00). Path: 0 -> 1 -> 2 (dropoff order 0, time=5+5=10). State: (loc=2, p_mask=0b01, d_mask=0b01). Total time = 10.

Constraints

Constraints & assumptions

  • 1 <= n <= 50
  • 0 <= roads.length <= n * (n - 1) / 2
  • 0 <= u, v < n, u != v
  • 1 <= time <= 1000
  • 0 <= startLocation < n
  • 1 <= orders.length <= 8 (Let M = orders.length)
  • 0 <= pickupLocation, dropoffLocation < n
  • pickupLocation != dropoffLocation for any order.
  • All input locations are valid within 0 to n-1.
  • It's guaranteed that a path exists between any two necessary locations (start, pickups, dropoffs).

Out of scope

  • Traffic conditions or dynamic travel times.
  • Multiple delivery agents.
  • Real-time order updates.

What interviewers evaluate

  • Correctly modeling the problem as a shortest path search on a state graph.
  • Efficiently computing all-pairs shortest paths between relevant locations.
  • Properly managing the state using bitmasks to track picked-up and delivered orders.
  • Applying Dijkstra's algorithm (or a similar priority queue-based search) effectively.
  • Adherence to time and space complexity constraints for the given N and M values.

Loading editor...