P7013 [CERC2013] History course

You are to give a series of lectures on important historical events, one event per lecture, in some order. Each event lasted for some time interval $[a_i, b_i].$ We say that two events are related if their intervals have a common point. It would be convenient to schedule lectures on related events close to each other. Moreover, lectures on unrelated events should be given in the order in which the events have taken place (if an event A preceded an unrelated event $B$ , then the lecture on A should precede the lecture on $B)$ . Find the minimum integer $k \ge 0$ and an order of the lectures such that any two related events are scheduled at most $k$ lectures apart from each other (lectures number $i$ and $j$ are considered to be $|i−j|$ lectures apart).

无

无

Time limit: 10 s, Memory limit: 128 MB. 感谢 [hht2006](/user/175829) 提供的 Special Judge。