We will use the notation from the task text: ~(a_i)~ is the order in which the trains arrived at the station on the first day, and ~(b_i)~ is the order in which the trains left the station on the second day.

Let's create a sequence ~(c_i)~, such that ~c_i~ is equal to ~b_j~ for which ~a_j = i~. In other words, sort the order of departure of trains according to the order of arrival of trains.

For example, let the order of arrival of trains be 3 5 2 4 1, and the order of departure 3 2 5 1 4. Then ~c_1 = b_5 = 4~ because ~a_5 = 1~, ~c_2 = b_3 = 5~ because ~a_3 = 2~, ~c_3 = b_1 = 3~ because ~a_1 = 3~, ~c_4 = b_4 = 1~ because ~a_4 = 4~, and ~c_5 = b_2 = 2~ because ~a_2 = 5~. Therefore, the sequence ~(c_i) =~ 4 5 3 1 2.

Let's now look at the trains in the sequence ~(c_i)~. In the example above, trains ~c_1~ and ~c_2~ cannot be on the same platform because ~c_1 < c_2~, which means that train ~c_1~ would have to leave the station before train ~c_2~, which is impossible because train ~c_1~ arrived at the station before train ~c_2~. On the other hand, trains ~c_1~ and ~c_3~ can be on the same platform because ~c_1 > c_3~, which means that train ~c_3~ will want to leave the station before train ~c_1~, which is possible because train ~c_3~ arrived at the station after train ~c_1~. From this it follows that if we were to find a sequence such that ~c_{x_1} < c_{x_2} < \dots < c_{x_k}~, then we would need ~k~ platforms for those trains.

We have now reduced the task to finding the longest such sequence. This problem is known as the longest increasing subsequence. The solution to the task is the length of the longest increasing subsequence of the sequence ~(c_i)~. Note that the trains contained in that subsequence will be the first train on each of the platforms, and that it is possible to arrange the other trains on the platforms so that all trains can leave the station without being blocked by other trains. The overall time complexity is ~\mathcal{O}(n \log n)~.