Log inSign up
hardGeeksforGeeksNot Started

Assembly Line Scheduling

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

An automobile factory has two assembly lines, each with n stations. Station j on line i is denoted as S_{i,j}.

- The processing time at station S_{1,j} is a[0][j], and at S_{2,j} is a[1][j]. - Entering line 1 takes entry time e[0], and entering line 2 takes e[1]. - Exiting line 1 takes exit time x[0], and exiting line 2 takes x[1]. - A car chassis can continue on the same line to station j+1 with zero transfer cost, or transfer to the other line with transfer cost t[0][j] (from line 1 to line 2) or t[1][j] (from line 2 to line 1). Note that t has size 2 × (n - 1).

Determine the minimum total time required to build a car chassis through all n stations and exit the factory.

### Example - Input: - a = [[4, 5, 3, 2], [2, 10, 1, 4]] - t = [[7, 4, 5], [9, 2, 8]] - e = [10, 12], x = [18, 7] - Output: 35 - Explanation: - Enter Line 2: 12 + 2 = 14 - Transfer to Line 1: 14 + 2 (t[1][0] wait, no transfer: stay on line 2 -> 14 + 10 = 24, or switch: 14 + 9 + 5 = 28) - Optimal path yields minimum cost of 35 upon exiting.

Constraints:

  • 1 <= n <= 105
  • 0 <= a[i][j] <= 1000
  • 0 <= t[i][j] <= 1000
  • 0 <= e[i], x[i] <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model multi-track pipelines as stage-wise state machines.
  • Derive mutually recursive DP state transitions between parallel lines.
  • Optimize state tables to O(1) memory variables.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Multiple parallel tracks or lines with switching penalties.
  • Sequential stage-by-stage pipeline processing.
  • Minimizing total transition and processing time.

Algorithmic Decision Tree:

  • Maintain running best cost for ending at each track at stage j.
  • Since transitions are only forward between adjacent stages, no backward loops exist.

Connected Patterns:

Paint HouseHouse RobberDynamic Programming on DAG

1. Recursive Exploration of All Line Choices

Intuition

At every station, branch into either staying on the current line or switching to the opposite line. Base case reaches station n and adds exit times.

Algorithm

  1. Define findMin(station, currentLine).
  2. If station == n - 1, return a[currentLine][station] + x[currentLine].
  3. Option 1: stay on currentLine -> cost is a[currentLine][station] + findMin(station + 1, currentLine).
  4. Option 2: switch to 1 - currentLine -> cost is a[currentLine][station] + t[currentLine][station] + findMin(station + 1, 1 - currentLine).
  5. Return min(Option 1, Option 2).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int solveRec(int j, int line, int n, const vector<vector<int>>& a, const vector<vector<int>>& t, const vector<int>& x) {
8 if (j == n - 1) {
9 return a[line][j] + x[line];
10 }
11 int stay = a[line][j] + solveRec(j + 1, line, n, a, t, x);
12 int transfer = a[line][j] + t[line][j] + solveRec(j + 1, 1 - line, n, a, t, x);
13 return min(stay, transfer);
14}
15
16int carAssemblyRecursive(int n, const vector<vector<int>>& a, const vector<vector<int>>& t, const vector<int>& e, const vector<int>& x) {
17 int startLine1 = e[0] + solveRec(0, 0, n, a, t, x);
18 int startLine2 = e[1] + solveRec(0, 1, n, a, t, x);
19 return min(startLine1, startLine2);
20}
21
22int main() {
23 vector<vector<int>> a = {{4, 5, 3, 2}, {2, 10, 1, 4}};
24 vector<vector<int>> t = {{7, 4, 5}, {9, 2, 8}};
25 vector<int> e = {10, 12};
26 vector<int> x = {18, 7};
27 cout << "Min Time (Recursive): " << carAssemblyRecursive(4, a, t, e, x) << endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) recursion call stack

2. 2D Tabulation DP

Intuition

Build two DP tables T1[n] and T2[n] where T1[j] stores the min time to reach station j on Line 1.

Algorithm

  1. Initialize T1[n] and T2[n].
  2. T1[0] = e[0] + a[0][0], T2[0] = e[1] + a[1][0].
  3. For j = 1 to n - 1:
  4. T1[j] = a[0][j] + min(T1[j - 1], T2[j - 1] + t[1][j - 1])
  5. T2[j] = a[1][j] + min(T2[j - 1], T1[j - 1] + t[0][j - 1])
  6. Return min(T1[n - 1] + x[0], T2[n - 1] + x[1]).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int carAssembly2D(int n, const vector<vector<int>>& a, const vector<vector<int>>& t, const vector<int>& e, const vector<int>& x) {
8 vector<int> T1(n), T2(n);
9 T1[0] = e[0] + a[0][0];
10 T2[0] = e[1] + a[1][0];
11
12 for (int j = 1; j < n; j++) {
13 T1[j] = a[0][j] + min(T1[j - 1], T2[j - 1] + t[1][j - 1]);
14 T2[j] = a[1][j] + min(T2[j - 1], T1[j - 1] + t[0][j - 1]);
15 }
16 return min(T1[n - 1] + x[0], T2[n - 1] + x[1]);
17}
18
19int main() {
20 vector<vector<int>> a = {{4, 5, 3, 2}, {2, 10, 1, 4}};
21 vector<vector<int>> t = {{7, 4, 5}, {9, 2, 8}};
22 vector<int> e = {10, 12};
23 vector<int> x = {18, 7};
24 cout << "Min Time (2D DP): " << carAssembly2D(4, a, t, e, x) << endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n) for tables T1 and T2

3. Constant Space O(1) Rolling Variables

Intuition

Since each station j only references the immediately preceding station j-1, maintain two scalar variables T1 and T2.

Algorithm

  1. T1 = e[0] + a[0][0], T2 = e[1] + a[1][0].
  2. For j = 1 to n - 1:
  3. nextT1 = a[0][j] + min(T1, T2 + t[1][j - 1])
  4. nextT2 = a[1][j] + min(T2, T1 + t[0][j - 1])
  5. T1 = nextT1, T2 = nextT2.
  6. Return min(T1 + x[0], T2 + x[1]).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int carAssemblyOptimal(int n, const vector<vector<int>>& a, const vector<vector<int>>& t, const vector<int>& e, const vector<int>& x) {
8 int T1 = e[0] + a[0][0];
9 int T2 = e[1] + a[1][0];
10
11 for (int j = 1; j < n; j++) {
12 int nextT1 = a[0][j] + min(T1, T2 + t[1][j - 1]);
13 int nextT2 = a[1][j] + min(T2, T1 + t[0][j - 1]);
14 T1 = nextT1;
15 T2 = nextT2;
16 }
17 return min(T1 + x[0], T2 + x[1]);
18}
19
20int main() {
21 vector<vector<int>> a = {{4, 5, 3, 2}, {2, 10, 1, 4}};
22 vector<vector<int>> t = {{7, 4, 5}, {9, 2, 8}};
23 vector<int> e = {10, 12};
24 vector<int> x = {18, 7};
25 cout << "Min Time (Optimal O(1) Space): " << carAssemblyOptimal(4, a, t, e, x) << endl;
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive SearchO(2^n)O(n)Branching choice for each station.Redundant subtrees
2.2D TabulationO(n)O(n)Table storing optimal entry to each station on line 1 and 2.Array space
3.Rolling VariablesOptimalO(n)O(1)Track only current T1 and T2 scalars.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting exit times x[0] and x[1] when computing the final answer.

Pitfall 2:

Off-by-one with transfer indices: t[0][j-1] corresponds to transfer from station j-1 to station j.

Pitfall 3:

Overwriting T1 before calculating T2: Updating T1 in place will corrupt the T2 calculation unless temporary variables are used.

Crucial Edge Cases to Validate:

  • n = 1: Single station on each line. Output is min(e[0] + a[0][0] + x[0], e[1] + a[1][0] + x[1]).
  • Transfer times t[i][j] are 0: Switching lines carries no penalty.
  • Transfer times extremely high: Algorithm will strictly stay on the line with lowest cumulative station cost.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Cite this problem as the canonical CLRS DP chapter opening example.
  2. Explain how Paint House and House Robber follow identical two-state or three-state transition principles.
  3. If asked to print the actual stations used, show how maintaining a prev_line[2][n] table allows tracing back.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can the space complexity of Assembly Line Scheduling be reduced to O(1)?

Back to DSA Sheet