Assembly Line Scheduling Problem

Problem Statement

A car factory has 2 assembly lines, each with n stations. Each station takes some time, and switching between lines has a transfer cost. Find the minimum time to assemble a car from start to end.

Example:

• Input: a[][] = {{4,5,3,2},{2,10,1,4}}, t[][] = {{0,7,4,5},{0,9,2,8}}, entry = {10,12}, exit = {18,7}
• Output: 35 (minimum time through the factory)

Noob-Friendly Explanation

Picture a car factory with two conveyor belts (Line 1 and Line 2), each having stations where workers do jobs. At each station, you can either stay on the same line or switch to the other line (which takes extra time). There's also a time to get on each line at the start and to get off at the end. You want to find the fastest route through the factory — sometimes it's worth switching lines if the other one is faster at that station!

Approach 1: Brute Force (Recursion)

Intuition

At each station, you have 2 choices: stay on the current line or switch. Try all combinations and pick the fastest.

Algorithm

1. At station j on line i, you either came from line i (no switch) or line 1-i (with switch cost)
2. Recurse for all stations and pick the minimum

public class Solution {
    public int solve(int[][] a, int[][] t, int[] entry, int[] exit, int line, int station) {
        // Base case: first station
        if (station == 0) {
            return entry[line] + a[line][0];
        }

        // Stay on same line
        int stayCost = solve(a, t, entry, exit, line, station - 1) + a[line][station];

        // Switch from other line
        int otherLine = 1 - line;
        int switchCost = solve(a, t, entry, exit, otherLine, station - 1)
                       + t[otherLine][station] + a[line][station];

        return Math.min(stayCost, switchCost);
    }

    public int assemblyLine(int[][] a, int[][] t, int[] entry, int[] exit, int n) {
        int line1 = solve(a, t, entry, exit, 0, n - 1) + exit[0];
        int line2 = solve(a, t, entry, exit, 1, n - 1) + exit[1];
        return Math.min(line1, line2);
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - At each station, we branch into 2 choices
• Space Complexity: O(n) - Recursion stack depth equals number of stations

Approach 2: Optimal (Iterative DP)

Intuition

Track the minimum time to reach each station on both lines. At each station, the optimal time is the min of staying on the same line or switching from the other line. We only need the previous station's values.

Algorithm

1. Initialize: dp1 = entry[0] + a[0][0], dp2 = entry[1] + a[1][0]
2. For each station j from 1 to n-1:
   • new1 = min(dp1 + a[0][j], dp2 + t[1][j] + a[0][j])
   • new2 = min(dp2 + a[1][j], dp1 + t[0][j] + a[1][j])
3. Answer = min(dp1 + exit[0], dp2 + exit[1])

public class Solution {
    public int assemblyLine(int[][] a, int[][] t, int[] entry, int[] exit, int n) {
        int dp1 = entry[0] + a[0][0];
        int dp2 = entry[1] + a[1][0];

        for (int j = 1; j < n; j++) {
            int newDp1 = Math.min(
                dp1 + a[0][j],              // stay on line 1
                dp2 + t[1][j] + a[0][j]     // switch from line 2
            );
            int newDp2 = Math.min(
                dp2 + a[1][j],              // stay on line 2
                dp1 + t[0][j] + a[1][j]     // switch from line 1
            );
            dp1 = newDp1;
            dp2 = newDp2;
        }

        return Math.min(dp1 + exit[0], dp2 + exit[1]);
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass through all stations
• Space Complexity: O(1) - Only two variables tracked