I: Sort the valid 2 * N - 1 intervals by their weight. Let's enumerate the minimum and find the corresponding maximum. Consider a simpler problem: Given some intervals (L_i, R_i], find whether we can cover the interval (0, N] without overlapping. It's equivalent to finding whether we can reach N from 0 by the edges . Because the length of a interval is at most 2, we can maintain a segment tree, where the segment [L, R] stores the connectivity between [L, L + 1] * [R - 1, R]. It's easy to merge the information. Using a 2-pointer and maintaining the connectivity dynamically, we can solve the problem in .

Can we use Dinic algorithm directly on the graph with N*N nodes? I think it will take the shortest path each time but I got a WA :( Is that correct?