Assembly Line Scheduling Problem

The problem, simply

A car factory has two lines, line A and line B. Each line has n stations in a row, and the car must visit station 1, then station 2, and so on up to station n. You can use either line for each station.

You get:

• a[line][j]: how long the job at station j takes on that line.
• t[line][j]: how long it takes to walk from line (after station j - 1) over to the other line, arriving at station j. Staying on the same line costs nothing.
• entry[line] and exit[line]: the time to get onto a line at the start and off it at the end.

Give back the smallest total time to build one car.

A story to remember it

Picture it

Examples

Way 1: the simple way

Ask a question backwards: "what is the fastest way to finish station j on line L?" There are only two ways to arrive:

1. You were on line L at station j - 1 and stayed. Cost: best of that, plus the job here.
2. You were on the other line at station j - 1 and walked over. Cost: best of that, plus the walk, plus the job here.

Station 1 is the floor of the question: the answer is entry[L] + a[L][0]. Ask the question for the last station on both lines, add the exit times, and take the smaller one.

class Solution {
    // fastest time to finish station j on line L
    int best(int[][] a, int[][] t, int[] entry, int L, int j) {
        if (j == 0) return entry[L] + a[L][0];
        int other = 1 - L;
        int stay = best(a, t, entry, L, j - 1) + a[L][j];
        int hop = best(a, t, entry, other, j - 1) + t[other][j] + a[L][j];
        return Math.min(stay, hop);
    }

    public int carAssembly(int[][] a, int[][] t, int[] entry, int[] exit) {
        int n = a[0].length;
        int viaA = best(a, t, entry, 0, n - 1) + exit[0];
        int viaB = best(a, t, entry, 1, n - 1) + exit[1];
        return Math.min(viaA, viaB);
    }
}

How long it takes: every question asks two smaller questions, so the calls double at each station, O(2^n). Extra room: the chain of waiting calls is n long, O(n).

Way 2: the clever way

The tree above asks about the same station again and again. So work forwards instead and write each answer down once, like the notes on the doors.

1. Fill station 1 on both lines: entry + job time.
2. For each next station, fill line A from the two boxes to its left (stay or hop), then line B the same way.
3. At the end add the exit times and take the smaller one.

Each column only needs the column before it, so two numbers are enough. We never need the whole table.

class Solution {
    public int carAssembly(int[][] a, int[][] t, int[] entry, int[] exit) {
        int n = a[0].length;
        int bestA = entry[0] + a[0][0];   // note on the door of A1
        int bestB = entry[1] + a[1][0];   // note on the door of B1
        for (int j = 1; j < n; j++) {
            // stay on the line, or walk over from the other line
            int nextA = Math.min(bestA + a[0][j], bestB + t[1][j] + a[0][j]);
            int nextB = Math.min(bestB + a[1][j], bestA + t[0][j] + a[1][j]);
            bestA = nextA;                // use the old values for both,
            bestB = nextB;                // then move them forward together
        }
        return Math.min(bestA + exit[0], bestB + exit[1]);
    }
}

How long it takes: one pass over the stations with a little work each, O(n). Extra room: two numbers, O(1).

Watch out for

• Mixing up the walk index. t[1][j] is the walk from line B over to line A at station j. Check which line you leave from.
• Forgetting entry or exit. A route that is fast inside the factory can still lose because of a slow exit.
• Some versions give the walk times as n - 1 numbers starting at station 2. Shift the index, do not guess.

What interviewers ask next

• Print the route, not just the time. Keep a "came from" mark for every box, then follow the marks back from the end, as in the last frame above.
• What if there are k lines? Each box looks at all k boxes in the column before, so it is O(n * k^2) time and O(k) room.
• Is this a shortest path problem? Yes. The map in "Picture it" has no loops, so going through the stations in order and relaxing each arrow once finds the shortest path.
• Can a car go backwards? Not here. If it could, there would be loops, and you would need Dijkstra instead of one forward pass.

Remember this

Grown-up words: the notes on the doors are the DP states, "stay or hop" is the recurrence, asking the same question again is overlapping subproblems, keeping only two numbers is space optimization, and the map with one-way arrows is a directed acyclic graph.