How should I practice Factory Cost — Minimum Cost Across Stages?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Stripe phone screen problems in FastPrep.

Is Factory Cost — Minimum Cost Across Stages associated with Stripe?

FastPrep tags this as a Stripe phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Dynamic Programming

Factory Cost — Minimum Cost Across Stages

Learn this problem

● Medium

StripeFULLTIMEPHONE SCREEN

See Stripe hiring insights

Problem statement

You are given production stages in stages. Each stages[i] contains the factories available for stage i. A factory is represented as [position, productionCost], where position is its location on a one-dimensional line.

Interview progression

Part 1

Ignore every factory position. Choose factories to minimize the total production cost.

Part 2

There are exactly three stages. Include the transit cost of moving the product between the selected factories. Moving between positions x and y costs |x - y|.

Part 3

The number of stages can be arbitrary. Minimize the sum of all selected production costs and all transit costs between consecutive stages.

Your task

Implement Part 3. Select exactly one factory from each stage. Stages are traversed in input order, and transit is charged only between factories selected from consecutive stages. There is no inbound transit before the first stage and no outbound transit after the last stage.

Return the minimum total cost as a signed 64-bit integer.

Function

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

Examples

Example 1

stages = [[[0,1],[10,4]],[[0,100],[10,4]],[[0,1],[10,4]]]return = 12

Select the factory at position 10 in every stage. The production cost is 4 + 4 + 4 = 12, and both transit costs are 0. Selecting the locally cheapest factories would cost 1 + 4 + 1 + 10 + 10 = 26, so the minimum is 12.

Example 2

stages = [[[-5,3],[4,6]],[[-2,4],[4,2]],[[1,4],[4,2]],[[3,3],[4,6]]]return = 14

Select positions 4, 4, 4, 3. Their production costs total 6 + 2 + 2 + 3 = 13, and transit costs 0 + 0 + 1 = 1, for a total of 14.

Example 3

stages = [[[-7,9],[3,2]]]return = 2

There is one stage, so there is no transit cost. Choose the factory whose production cost is 2.

Constraints

stages.length >= 1.
Every stages[i] contains at least one factory.
Every factory is represented by exactly two signed 32-bit integers: [position, productionCost].
Exactly one factory must be selected from each stage.
The minimum total cost fits in a signed 64-bit integer.