Assembly Line Scheduling
01 · Problem
A factory has two assembly lines, line 0 and line 1, each with n stations numbered 0 to n - 1. A product must pass through stations 0, 1, ..., n - 1 in order, visiting exactly one of the two lines at each station index.
a[i][j]is the time spent at stationjof linei.t[i][j](for0 <= j < n - 1) is the time to transfer the product from lineiright after stationjto the other line, before stationj + 1. Staying on the same line costs no transfer time.e[i]is the time to enter lineibefore station0.x[i]is the time to exit lineiafter stationn - 1.
Return the minimum total time to build one product. When n == 1, t is [[],[]].
02 · Examples
a = [[4,5,3],[2,10,1]], t = [[7,4],[9,2]], e = [10,12], x = [18,7]
31
Enter line 0 (10), stations 0 and 1 on line 0 (4 + 5), transfer to line 1 after station 1 (4), station 2 on line 1 (1), exit line 1 (7): 10 + 4 + 5 + 4 + 1 + 7 = 31.
a = [[3,2,6],[5,1,4]], t = [[2,3],[1,2]], e = [1,2], x = [3,1]
12
Enter line 0 (1), station 0 on line 0 (3), transfer to line 1 (2), stations 1 and 2 on line 1 (1 + 4), exit line 1 (1): 1 + 3 + 2 + 1 + 4 + 1 = 12.
a = [[5],[6]], t = [[],[]], e = [2,1], x = [3,1]
8
With a single station, line 0 costs 2 + 5 + 3 = 10 and line 1 costs 1 + 6 + 1 = 8, so the answer is 8.
03 · Constraints
- 01a.length == 2 and 1 <= a[i].length == n <= 1000
- 02t.length == 2 and t[i].length == n - 1
- 03e.length == 2 and x.length == 2
- 041 <= a[i][j], t[i][j], e[i], x[i] <= 1000
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.