FastPrep
Problem · Dynamic Programming

Factory Cost Part 2 — Three Stages with Transit

Learn this problem
● MediumStripe logoStripeFULLTIMEPHONE SCREEN
See Stripe hiring insights

Problem statement

A product must pass through exactly three production stages in order. For each stage, choose exactly one factory.

stages[i] lists the factories available at stage i. Each factory is [position, productionCost], where position is its coordinate on a one-dimensional line.

The total cost is the sum of the three selected production costs plus the transit costs between consecutive selected factories. Moving between positions x and y costs |x-y|. There is no inbound cost before stage 0 and no outbound cost after stage 2.

Return the minimum possible total cost.

Practice sequence

  1. Part 1: ignore positions and minimize production cost.
  2. Part 2: exactly three stages with transit cost (current).
  3. Part 3: arbitrary number of stages.

Function

findMinimumCostThreeStages(stages: int[][][]) → long

Examples

Example 1

stages = [[[20,100],[0,50],[1,30]], [[10,100],[2,20],[56,10]], [[10,10],[1,12],[3,5]]]return = 57
Choose [1,30], [2,20], and [3,5]. Production costs total 55 and transit costs total |1-2| + |2-3| = 2, for 57. Checking all combinations shows this is the minimum.

Example 2

stages = [[[0,10]], [[5,1],[1,8]], [[2,4]]]return = 23
Choosing stage-1 factory [1,8] costs 10 + 8 + 4 in production and |0-1| + |1-2| = 2 in transit, total 24; choosing [5,1] costs 10 + 1 + 4 + 5 + 3 = 23.

Constraints

  • stages.length == 3.
  • Every stage contains at least one factory.
  • Each factory is [position, productionCost].
  • Positions and production costs are integers; production costs are non-negative.
  • Return the result as a signed 64-bit integer.

More Stripe problems

drafts saved locally
public long findMinimumCostThreeStages(int[][][] stages) {
  // write your code here
}
stages[[[20,100],[0,50],[1,30]], [[10,100],[2,20],[56,10]], [[10,10],[1,12],[3,5]]]
expected57
checking account