Frontend School

Service Route with Dynamic Toolkit Load

DSA
hard

Service Route with Dynamic Toolkit Load

Hard
Dynamic Programming
2D DP
Grid Traversal
Optimization

Overview

Urban Company technicians often navigate complex city routes to provide services. To ensure efficient and reliable service delivery, it's crucial to minimize disruptions while effectively managing on-hand equipment. This problem models a technician traversing a city grid, optimizing their path to a client location while adhering to strict toolkit weight constraints, which dynamically change based on pickups and drop-offs along the route.

What you need to do / Task

You are given a city grid, where each cell represents a block with an associated disruption cost and a potential weight change to the technician's toolkit (due to picking up or dropping off parts). Your task is to find the minimum total disruption cost to travel from the top-left corner (0, 0) to the bottom-right corner (M-1, N-1).

  1. The technician starts at (0, 0) with a specified initialWeight.
  2. They can only move right or down.
  3. At each cell (r, c), they incur grid[r][c][0] disruption cost, and their toolkit weight changes by grid[r][c][1].
  4. The toolkit's weight must never exceed maxCapacity at any point during the journey, nor can it drop below 0.
  5. If no valid path exists, return -1.

Input & output

Function Signature: function findMinDisruption(grid: number[][][], initialWeight: number, maxCapacity: number): number

Parameters:

  • grid: A 2D array of dimensions M x N, where M is the number of rows and N is the number of columns. Each element grid[r][c] is a tuple [disruptionCost, weightChange].
    • disruptionCost: A non-negative integer representing the cost incurred when entering cell (r, c).
    • weightChange: An integer representing the change in toolkit weight when traversing cell (r, c). Positive for pickup, negative for drop-off, zero for no change.
  • initialWeight: A non-negative integer representing the toolkit's weight when starting at (0, 0). This weight is before applying grid[0][0][1]'s weightChange.
  • maxCapacity: A positive integer representing the maximum allowed weight for the toolkit.

Return Value:

  • A number representing the minimum total disruption cost to reach (M-1, N-1) while satisfying all constraints. Return -1 if no such path exists.

Clarifications

  • The disruption cost of the starting cell (0,0) is always incurred. The weightChange of (0,0) is also applied to initialWeight after entering the cell. The resulting weight must be valid.
  • The path must end at (M-1, N-1). The disruption cost and weight change of the final cell are included in the total.
  • The weight constraints (0 <= currentWeight <= maxCapacity) apply after the weightChange of the current cell has been applied. If applying weightChange violates the constraint, that path becomes invalid from that point.

Examples

1

Example 1

Input:

grid = [[[10, 0], [20, 0]], [[30, 0], [40, 0]]], initialWeight = 5, maxCapacity = 10

Output:

70

Note:

The technician starts at (0,0) with weight 5. Path 1: (0,0) -> (0,1) -> (1,1)

  • At (0,0): Current weight 5. New weight: 5 + 0 = 5. Cost: 10. (Valid: 0 <= 5 <= 10)
  • At (0,1): Current weight 5. New weight: 5 + 0 = 5. Cost: 20. Total cost: 10 + 20 = 30. (Valid: 0 <= 5 <= 10)
  • At (1,1): Current weight 5. New weight: 5 + 0 = 5. Cost: 40. Total cost: 30 + 40 = 70. (Valid: 0 <= 5 <= 10) Path 2: (0,0) -> (1,0) -> (1,1)
  • At (0,0): Current weight 5. New weight: 5 + 0 = 5. Cost: 10. (Valid: 0 <= 5 <= 10)
  • At (1,0): Current weight 5. New weight: 5 + 0 = 5. Cost: 30. Total cost: 10 + 30 = 40. (Valid: 0 <= 5 <= 10)
  • At (1,1): Current weight 5. New weight: 5 + 0 = 5. Cost: 40. Total cost: 40 + 40 = 80. (Valid: 0 <= 5 <= 10) The minimum disruption cost is 70.
2

Example 2

Input:

grid = [[[10, 2], [5, -3]], [[15, 0], [20, 1]]], initialWeight = 5, maxCapacity = 7

Output:

35

Note:

The technician starts at (0,0) with weight 5. Path 1: (0,0) -> (0,1) -> (1,1)

  • At (0,0): Current weight 5. New weight: 5 + 2 = 7. Cost: 10. (Valid: 0 <= 7 <= 7)
  • At (0,1): Current weight 7. New weight: 7 + (-3) = 4. Cost: 5. Total cost: 10 + 5 = 15. (Valid: 0 <= 4 <= 7)
  • At (1,1): Current weight 4. New weight: 4 + 1 = 5. Cost: 20. Total cost: 15 + 20 = 35. (Valid: 0 <= 5 <= 7) Path 2: (0,0) -> (1,0) -> (1,1)
  • At (0,0): Current weight 5. New weight: 5 + 2 = 7. Cost: 10. (Valid: 0 <= 7 <= 7)
  • At (1,0): Current weight 7. New weight: 7 + 0 = 7. Cost: 15. Total cost: 10 + 15 = 25. (Valid: 0 <= 7 <= 7)
  • At (1,1): Current weight 7. New weight: 7 + 1 = 8. This path is invalid as 8 > maxCapacity (7). The minimum disruption cost is 35.
3

Example 3

Input:

grid = [[[1, 10]], [[1, 10]]], initialWeight = 0, maxCapacity = 5

Output:

-1

Note:

The technician starts at (0,0) with weight 0. At (0,0): Current weight 0. New weight: 0 + 10 = 10. This is invalid as 10 > maxCapacity (5). Since the initial step violates the capacity constraint, no valid path can be formed.

Constraints

Constraints & assumptions

  • 1 <= M, N <= 50 (grid dimensions)
  • 0 <= disruptionCost <= 1000 for any cell (r, c)
  • -500 <= weightChange <= 500 for any cell (r, c)
  • 0 <= initialWeight <= maxCapacity
  • 1 <= maxCapacity <= 1000
  • All disruptionCost values are integers.
  • All weightChange values are integers.
  • All initialWeight, maxCapacity values are integers.

What interviewers evaluate

  • Correctness and Optimality: The solution correctly identifies the minimum disruption cost or determines if no path exists, adhering to all constraints.
  • Dynamic Programming Application: Effective use of 2D (or 3D) dynamic programming to solve the problem efficiently.
  • Edge Cases and Constraints: Proper handling of boundary conditions, including grid edges, initial/final weights, and capacity limits.
  • Code Quality: Readability, modularity, and maintainability of the implemented solution.

Loading editor...