1421: 乐乐的工作

    乐乐非常喜欢现在这份工作，因为公司只要求员工把每天的工作完成，不要求固定的上班时间。假如乐乐的同事有的从300时刻（以秒为单位），一直工作到3000时刻（我们认为从300时刻工作到3000时刻所工作的时间为3000-300=2700秒，即结束的那个时刻是没有工作的）；有的从700时刻开始，在5200时刻结束；有的从6500时刻开始，到8100时刻结束。那么期间最长的至少有一个人在工作的连续时间是4900秒（从300时刻到5200时刻），而最长的无人工作的连续时间为1300时刻（从5200时刻到6500时刻）。

    现在乐乐想知道从最早有人开始工作的时间至最后一个人离开的时间里，公司里最长至少有一人在工作的时间段和最长的无人工作的时间段。

    第一行一个整数n(1≤n≤5000)；

    接着有n行，每行有两个用空格分开的正整数Ai和Bi(0≤Ai<Bi≤1000000)。

3
300 3000
700 5200
6500 8100

4900 1300

【问题分析】

    有n个人，每个人从时刻i开始工作，到时刻j结束，从最早开始的人开始的时刻算起，至少有一个人工作的连续时间段的最大值，和一个人也不工作的时间段的最大值。

【样例解释】

    样例一：最长至少有一个人工作的连续时间段的最大值即从300到5200，一个人也不工作的时间段的最大值即从5200 到6500。

【算法分析】

    从数据看,bi<=1000000，n<=5000,如果标记每个时刻是否有人工作，最坏情况时间复杂度O（n*10^6），超的一塌糊涂。预计60分。（这个数据有点水，原题是时刻小于maxlongint）。

    仔细思考不难发现，如果n[i]开始的时间小于等于n[j]结束的时间，那么n[i]会和n[j]相重合一部分就可以更新前者的结束时间。如果再按照开始时间排序，那么这就是一个单调上升的序列。一旦n[i]开始时间大于n[j]结束时间，那么这段空隙一定是无人工作的，前面那一段时间必定是一直有人工作的。

但要注意一点比如：

10 50

20 30

40 50

    虽然第一个到的是50，但第二个只有30<40，这个时候就要与目前能达到的最大时间做比较。或者你更新最前面一个的时间，一直于最前面一个的结束时间做比较。那么就有了一个算法，先排序，再模拟，时间复杂度O(n log(n)+n)