Frontend School

Drone Delivery Optimization with Limited Boosts

DSA
medium

Drone Delivery Optimization with Limited Boosts

Medium
Graph
Shortest Path
Dijkstra
Priority Queue

Overview

In the rapidly evolving world of logistics, drone delivery networks are becoming crucial for efficient package transportation. A key challenge is optimizing delivery routes to minimize travel time while managing valuable resources. Our drone fleet has access to standard routes, but each drone is also equipped with a limited number of 'boosts' that can significantly reduce travel time on any segment. Your task is to design an algorithm to find the fastest possible route from a starting depot to a destination, leveraging these boosts strategically.

What you need to do / Task

Implement the function minBoostedTravelTime that calculates the minimum time required for a drone to travel from a startNode to an endNode within a given network. The drone has a maximum of k boosts available to use across its entire journey. Each boost can be applied to exactly one segment of the path, reducing its travel time from time to boostTime.

Input & output

Function Signature:

function minBoostedTravelTime(n: number, edges: number[][], startNode: number, endNode: number, k: number): number

Parameters:

  • n: An integer representing the total number of locations (nodes) in the network, indexed from 0 to n-1.
  • edges: A 2D array of integers, where each inner array [u, v, time, boostTime] represents an undirected road segment between location u and location v. time is the normal travel duration, and boostTime is the travel duration if a boost is used on this segment.
  • startNode: An integer representing the starting location of the drone.
  • endNode: An integer representing the target destination of the drone.
  • k: An integer representing the maximum number of boosts available for the entire journey.

Return Value:

  • An integer representing the minimum total time to reach endNode from startNode using at most k boosts. If endNode is unreachable, return -1.

Clarifications

  • All time and boostTime values are positive integers.
  • boostTime for any segment is always strictly less than its time.
  • The graph is undirected, meaning if there's an edge [u, v, time, boostTime], travel from v to u also takes time or boostTime.
  • It's possible that startNode equals endNode; in this case, the time is 0.
  • If no path exists, return -1.

Examples

1

Example 1

Input:

n = 3, edges = [[0,1,10,2],[1,2,5,1]], startNode = 0, endNode = 2, k = 1

Output:

7

Note:

Path 0 -> 1 (boosted) -> 2 (normal). Time: 2 + 5 = 7. (1 boost used) Path 0 -> 1 (normal) -> 2 (boosted). Time: 10 + 1 = 11. (1 boost used) Path 0 -> 1 (normal) -> 2 (normal). Time: 10 + 5 = 15. (0 boosts used) Minimum is 7.

2

Example 2

Input:

n = 4, edges = [[0,1,10,2],[0,2,20,5],[1,3,15,3],[2,3,8,1]], startNode = 0, endNode = 3, k = 2

Output:

5

Note:

Consider paths from 0 to 3:

  1. 0 -> 1 -> 3:
    • No boosts: 10 + 15 = 25
    • Boost 0-1 (1 boost): 2 + 15 = 17
    • Boost 1-3 (1 boost): 10 + 3 = 13
    • Boost both (2 boosts): 2 + 3 = 5
  2. 0 -> 2 -> 3:
    • No boosts: 20 + 8 = 28
    • Boost 0-2 (1 boost): 5 + 8 = 13
    • Boost 2-3 (1 boost): 20 + 1 = 21
    • Boost both (2 boosts): 5 + 1 = 6 The minimum time is 5.
3

Example 3

Input:

n = 2, edges = [[0,1,100,10]], startNode = 0, endNode = 1, k = 0

Output:

100

Note:

With 0 boosts, only the normal travel time applies: 100.

4

Example 4

Input:

n = 3, edges = [[0,1,10,2]], startNode = 0, endNode = 2, k = 1

Output:

-1

Note:

Node 2 is unreachable from node 0.

Constraints

Constraints & assumptions

  • 1 <= n <= 100
  • 0 <= edges.length <= n * (n - 1) / 2
  • 1 <= time, boostTime <= 1000 for any edge.
  • boostTime < time for any edge.
  • 0 <= startNode, endNode < n
  • 0 <= k <= n
  • The graph may not be connected.
  • There will be at most one edge between any pair of nodes (u, v).

Out of scope

  • Handling negative time or boostTime values.
  • Dynamic changes to the network or boost availability during travel.

What interviewers evaluate

  • Correctness: The solution must correctly identify the minimum travel time under all valid inputs and edge cases (e.g., k=0, unreachable destination).
  • Algorithm Design: Demonstrates an understanding of graph traversal and shortest path algorithms, adapting them for state-based constraints.
  • Time and Space Complexity: Provides an optimal solution with reasonable time and space complexity for the given constraints.
  • Code Quality: Produces clean, readable, and well-structured code with appropriate variable names and comments where necessary.

Loading editor...