Sort two list of jobs result in minimum execution time

Question

Two twins, James Johnson and Jonathan Johnson, work at a factory which produces bicycles. Their job is probably the most important one: James attaches the front wheel, and Jonathan does the same with the rear wheel. At the beginning of their working day, they receive construction kits, consisting of the front wheel, the rear wheel, and the rest of the bicycle. It is known that:

• for the i-th construction kit, James will attach the front wheel in Ai seconds;
• for the i-th construction kit, Jonathan will attach the rear wheel Bi in seconds;
• James and Jonathan cannot work on the same bicycle simultaneously;
• the front wheel must be attached earlier than the rear wheel.

James and Jonathan are very experienced in assembling bicycles. In fact, given the information about all construction kits, they act optimally, such that the last wheel is attached as early as possible. However, the new director of the factory is not yet that experienced, so she needs some help. Please write her a program which tells how fast the twins assemble all today's bicycles, and how exactly this could be done.

Input

The first line of the input file contains N, the number of bicycle construction kits.

The second line contains N integers, the i-th of them equals Ai. The third line also contains N integers, the i-th of them equals Bi. All Ai and Bi are positive and do not exceed 10^9.

Output

In the first line, output the minimum time needed to assemble all bicycles.

The second line must contain integers. Of them, the i-th integer denotes the moment of time James starts to assemble the i-th construction kit. The third line must contain integers, this time for Jonathan. If several optimal scenarios exist, output any of them.

Examples

input.txt 3

1 2 3

2 1 3

output.txt 8

0 4 1

1 7 4

My solution is a greedy approach, sorting the sequences of pair (Ai, Bi) and (Ai+1, Bi+1). If execute the sequence in order i+1 -> i takes less time that i -> i+1, then swap them. So far it passes 13 test cases and fails on a test case with quite close result. The expected output is 29 while my solution yields 31. If anybody can help please give me a hint, thank you in advance.

I use Java, I implement a class called Job which stores a pair of Ai, Bi and the original index.

static class Job implements Comparable<Job> {
    long a;
    long b;
    int index;

    public Job(long a, long b, int index) {
        this.a = a;
        this.b = b;
        this.index = index;
    }

    @Override
    public int compareTo(Job that) {
        long thisTime = this.a + Math.max(this.b, that.a) + that.b;
        long thatTime = that.a + Math.max(this.a, that.b) + this.b;

        return Long.compare(thisTime, thatTime);
    }

    @Override
    public String toString() {
        return "(" + a + "," + b + ") - " + index;
    }
}

public static void solve(long[] a, long[] b, int[] order) throws IOException {
    long[][] start = new long[2][a.length];
    int prev = -1;
    for (int i : order) {
        if (prev == -1) {
            start[0][i] = 0;
            start[1][i] = a[i];
        } else {
            start[0][i] = start[0][prev] + a[prev];
            start[1][i] = Math.max(start[1][prev] + b[prev], start[0][i] + a[i]);
        }

        prev = i;
    }

    long time = start[1][prev] + b[prev];
    bw.write(time + "\n");
    for (int i = 0; i < start.length; ++i) {
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < start[0].length; ++j)
            sb.append(start[i][j] + " ");
        bw.write(sb.toString().trim() + "\n");
    }
}

Answer 1

This is a job shop scheduling problem. We can view James and Jonathon as two machines, each of which performs a specific process. Each job requires two processes performed in the same order for every job.

Although job shop scheduling is NP-complete in general, the two-machine instance can be solved in polynomial time by Johnson's rule.