307. Assembly Line Scheduling Problem

A car chassis passes through n stations on each of two parallel assembly lines. Given the entry time onto each line, the exit time off each line, the time to process the chassis at station i on each line, and the cost to transfer the chassis from one line to the other right after station i (for i from 1 to n-1), find the minimum total time to build one chassis from entry to exit.

Input: Seven lines: n; the two entry times (line 1, line 2); the two exit times (line 1, line 2); n station times for line 1; n station times for line 2; n-1 transfer costs into line 1; n-1 transfer costs into line 2. Output: Print a single integer - the minimum total time to build one chassis from entry to exit.

1 <= n <= 1000

This is a clean example of a DP problem with TWO parallel 'states' (which line you're on) at each step - the same pattern (tracking a small, fixed number of parallel running values, each depending only on the PREVIOUS step's values) generalizes to many other 'choose between a few options at each stage' DP problems.

Find the minimum total time to build a chassis moving through two parallel assembly lines, with costs to switch lines between stations. Brute force: Try every possible sequence of line-switching decisions directly at each station - this is exponential (2^n possible line-choice sequences), impractical for n up to 1000. Optimised: Since the minimum time to reach the end of station i on either line only depends on the minimum times to reach the END of station i-1 on BOTH lines, building the table left to right (station by station) computes each station's best times exactly once, reused directly by the next station.

Cache the minimum time to reach station i on line 1 and the minimum time to reach station i on line 2 the first time each is computed. Since there are only 2n such (station, line) states total, and each one is computed in constant time from the cached result of the previous station, caching eliminates all the repeated recomputation from the brute force and brings the total work down to linear in the number of stations, while keeping the same recursive structure. Time: O(n) Space: O(n)

At each station, the chassis is on one of the two lines, and recursively, the minimum time to reach that station on that line is the minimum time to reach the previous station on either line (paying a transfer cost if switching lines) plus this station's processing time. Exploring this choice recursively for both lines at every station, all the way back to the entry points, correctly computes the minimum total build time, but it recomputes the best time to reach earlier stations repeatedly across different branches, doubling the work at every step back. Time: O(2^n) Space: O(n) for the recursion stack

Compute the minimum time to reach each station iteratively from the entry point forward, station by station, on both lines at once. Because the minimum time to reach station i only ever depends on the minimum times to reach station i-1 on both lines, there is no need to keep a full table of all n stations - just two running values (best time so far on line 1, best time so far on line 2) that get updated and overwritten as the iteration moves forward, finishing with the smaller of the two exit times added on. This keeps the linear time of the memoized version but drops the memory needed to constant. Time: O(n) Space: O(1)

1. Let T1[i] and T2[i] be the minimum time to reach the end of station i on line 1 and line 2 respectively. 2. T1[0] = entry1 + a1[0]; T1[i] = min(T1[i-1]+a1[i], T2[i-1]+transferToLine1[i-1]+a1[i]), and symmetrically for T2. 3. The final answer is min(T1[n-1]+exit1, T2[n-1]+exit2).

Time: O(n) - one single pass through the n stations, computing both lines' times at each step. Space: O(n) for the full T1/T2 arrays (reducible to O(1) with just the previous station's two values).

Test n = 1 (no transfer costs exist, answer is simply the cheaper of the two entry+station+exit paths) and n = 1000 (upper bound) for the O(n) DP.

Be ready to explain the transfer-cost indexing carefully - the transfer cost 'into line 1 after station i' is what's paid when switching FROM line 2 TO line 1 between stations i and i+1, a detail easy to get backwards under pressure.