FastPrepUber Circular Shuttle Optimization

Uber Circular Shuttle Optimization

Uber logoUber● HardOA
Learn

Problem statement

Uber has launched a new circular shuttle service that operates on a fixed route, starting and ending at the same location while collecting passengers from various designated stops.

The service area consists of n pickup locations, numbered from 0 to n-1. These locations are interconnected by roads, each with a uniform travel cost of 1 unit. The road network is defined by n-1 edges, where each edge [ai, bi] represents a bidirectional road connecting locations ai and bi. This configuration forms a connected tree structure of pickup locations.

Passenger demand is represented by an array of size n, where passengers[i] equals 1 if there's a passenger waiting at location i, and 0 otherwise.

The shuttle service operates as follows: The shuttle may begin its route at any pickup location. Two operations are available at each stop:

  • Passenger Collection (Cost: 0): Collect all passengers within a radius of 2 roads from the current location. The radius represents the maximum number of road segments the shuttle can reach to pick up passengers without additional cost.
  • Movement (Cost: 1): Travel to any directly connected pickup point, incurring a cost of 1 unit per road segment.

Objective: Determine the minimum total cost required to collect all waiting passengers and return the shuttle to its starting location.

Important Constraints:

  • Each time a road segment is traversed, it contributes 1 unit to the total cost (meaning a round trip on the same road costs 2 units).
  • The pickup locations form a valid tree structure (connected and acyclic).

Goal: Find the optimal starting location and route strategy that minimizes the total operational cost.

Note: If you pass a road 2 times, the cost to traverse that road becomes 2.

Function

minimumShuttleCost(passengers: int[], edges: int[][]) → int

Complete the function minimumShuttleCost in the editor.

minimumShuttleCost has the following parameters:

  1. int[] passengers: A 1D array of integers where passengers[i] = 1 indicates a passenger at pickup point i, and passengers[i] = 0 indicates no passenger.
  2. int[][] edges: A 2D array of integers where edges[i] = [ai, bi] indicates a bidirectional road connecting ai and bi.

Returns int: Minimum cost incurred to start at a pickup point and return to the same starting point after collecting all the passengers from the pickup points.

Examples

Example 1

passengers = [1, 0, 0, 0, 0, 1]edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]return = 2

The Uber shuttle can follow the below steps to reduce the cost to 2 and collect all 2 passengers: Start at pick-up point 2 Collect the passenger from pick-up point 0 Move to adjacent pick-up point 3 Collect the passenger from pick-up point 5 Move back to adjacent pick-up point 2 Cost is incurred only during movement from pick-up points 2 to 3 and 3 to 2. Total cost = 2.

Example 2

passengers = [0, 0, 0, 1, 1, 0, 0, 1]edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]return = 2

The Uber shuttle can follow the below steps to reduce the cost to 2 and collect all 3 passengers: Start at pick-up point 0 Collect the passengers from pick-up points 3 and 4 Move to adjacent pick-up point 2 Collect the passenger from pick-up point 7 Move back to adjacent pick-up point 0 Cost is incurred only during movement from pick-up points 0 to 2 and 2 to 0. Total cost = 2.

Constraints

  • 1 ≤ n ≤ 3·10^4
  • passengers.size() equals n.
  • 0 ≤ passengers[i] ≤ 1
  • edges.length equals n-1.
  • edges[i].length equals 2.
  • 0 ≤ ai, bi < n
  • ai ≠ bi

More Uber problems

See Uber hiring insights
public int minimumShuttleCost(int[] passengers, int[][] edges) {
  // write your code here
}
passengers[1, 0, 0, 0, 0, 1]
edges[[0,1],[1,2],[2,3],[3,4],[4,5]]
expected2
Checking account…