# Job scheduling problem in O(n log n)

There are $n \leq 10^6$ kinds of cake layers, and for each kind we have a machine capable of baking it in one unit of time and nothing more. Now, a cake is a sequence of layers, more specificly a permutation of numbers $\{1,2,...,n\}$, and before doing one of layers in a cake all previous ones must have been done.

Given two cakes we want to find the shortest time sufficient for baking them both. Of course one machine can work only on one layer at a time, but different machines can work simultaneously. From this constraints we obtain that this time is between $n$ (at each moment the maximum number of two machines at work) and $2n$ (each layer done separately).

Let's take an example. We're given cakes $\{1,2,3\}$ and $\{3,2,1\}$. Baking them is possible in $4$ units of time - first we bake first layers from both cakes, next the middle layer of the first cake, then the middle layer of the second cake and the last of the first one, and lastly the one remaining layer. However, it's not possible to bake those cakes in time $3$, thus the desired answer is $3$.

What I tried was some dynamic programming, which leads to $O(n^2)$ solution. Then I tried expressing this problem as some kind of bipartie graph problem, which would be something like "how many edges can a bipartie graph of $n$ vertices on both sides have, if no two edges can cross, and also we're given some set of $n$ forbidden edges?". I could not go any further with this approach though. Also, I thought of transforming our two cakes in such a way that the first one is just $\{1,2,...,n\}$ - which is easy. Then, our problem can be thought as looking for some special subsequence in the second cake (after transformation), and then I tried to reduce it to longest increasing subsequence, but failed here as well.

What I ask for are hints for solving this problem in complexity around $O(n \log n)$.

• "it in" $\: \mapsto \:$ "it for one cake in" $\;\;\;$ ? $\;\;\;\;\;\;\;$ – user12859 Sep 26 '14 at 17:46
• Yes. A machine $i$ can bake layer $i$ for only one cake at a certain moment - see the example. – Cris Sep 26 '14 at 17:56
• Did you try finding a formula for the minimal time? How about a greedy algorithm? – Yuval Filmus Sep 26 '14 at 19:28
• The problem with greedy is the following - if in some time unit you hit two identical layers, then choosing which one to process first seems non-trivial... And if by a formula you mean something easy or straight-forward, then I doubt it's existance. – Cris Sep 26 '14 at 20:02