Factory network cost with stage-to-stage transport

A company is planning a chain of factories. Each factory has several candidate options, and you must pick exactly one option for every factory. The interview comes in parts; each part builds on the last.

Part 1: independent build costs

Implement min_build_cost(costs: list[list[int]]) -> int. costs[i] lists the build cost of each option for factory i. Rows may have different lengths. Return the minimum total build cost (the sum of the chosen options).

costs = [[4, 2, 7], [5], [3, 9]]
min_build_cost(costs)  # 10  (2 + 5 + 3)

Part 2: stages with transport cost

Now the factories are stages of one production line, in order. Each option is a site (position, build_cost) on a straight road. Goods built at stage i are shipped to the site chosen for stage i + 1, which costs |x - y| for positions x and y.

Implement min_network_cost(stages: list[list[tuple[int, int]]]) -> int. Return the minimum of (sum of build costs of the chosen sites) + (sum of transport costs between consecutive stages). Start with three stages.

stages = [
    [(0, 5), (10, 1)],   # stage 0
    [(3, 2), (9, 6)],    # stage 1
    [(4, 1)],            # stage 2
]
min_network_cost(stages)  # 12
# 0 -> 3 -> 4 costs 5 + 2 + 1 to build plus 3 + 1 to ship = 12.
# 10 -> 3 -> 4 also costs 12. The cheapest first site is not automatically best.

Part 3: any number of stages, many sites

Support any number of stages. The total number of sites K across all stages can be up to 10^5, positions are integers in [-10^9, 10^9] and build costs are in [0, 10^9]. A solution that compares every pair of sites between consecutive stages is too slow when one stage has many sites.

Constraints for all parts: every factory or stage has at least one option. An empty input returns 0.

Reconstructed from the reported question; details may differ from what interviewers ask.