Description

瓦特尔，阿隆索，汉密尔顿在F1上海站进行比赛，每人必须进维修站更换轮胎一次（谁出的无聊规定？！），而且只能进维修站一次。

阿隆索在20秒进站换胎，一直到90秒出站。瓦特尔在60秒开始进站，在 130秒结束。汉密尔顿在160秒开始220秒结束。期间最长的至少有一个车手在维修区的连续时间为110秒(从20秒到130秒)，而最长的无人在维修区的连续时间(从有人进维修站开始一直到出维修站)为30秒(从130秒到160秒)。

假设现在又进行了一场有N个车手的比赛，你的任务是编一个程序，读入一个有N个车手(1 <= N <= 5000)进N次站的工作时间列表，计算以下两点(均以秒为单位):

最长至少有一人在维修站内的时间段。

最长的无人在维修站的时间段。（从有人进站开始算起）

Input Format

第1行:一个整数N。

第2至第N+1行:每行两个小于1000000的非负整数，表示一个车手的进站时刻与出站时刻。

Output Format

一行，两个整数，即题目所要求的两个答案。

Sample Input

3200 900600 13001600 2200

Sample Output

1100 300 最直觉的想法是把可以合并的连续有车的时间合并起来,算作一个时间段,构建一个只有不重合且不连续的若干个区间,然后就可以很容易的得到答案了. 构建的时候,可以考虑首先把这些区间(按照开始时间的先后)排序,方便逻辑处理. 在合并的过程中,对两个区间进行分类讨论. 有交叉(相等) 包含 或者根本无交集.

#include 
     
      #include 
      
        using namespace std;struct carPeriod{    int start;    int end;};carPeriod cars[5001];carPeriod newcars[5001];int cmp_carperiod_1(const void* _a, const void* _b){    carPeriod* a = (carPeriod*) _a;    carPeriod* b = (carPeriod*) _b;    return (*a).start - (*b).start;} int main(int argc, char const *argv[]){        int N;cin>>N;    for (int i = 0; i < N; ++i)        cin>>cars[i].start>>cars[i].end;    int maxIN=0, maxOUT=0;     qsort(cars, N, sizeof(carPeriod),cmp_carperiod_1);//根据进入的时间排序    int newN = 0;//新时间段的个数    newcars[newN].start = cars[0].start; //第一个时间段    newcars[newN].end = cars[0].end;    //目标: 把所有的有交集的时间段组合起来    for (int i = 1; i < N; ++i)    {        if(cars[i].start <= newcars[newN].end and cars[i].end >= newcars[newN].end){
   //交叉关系            newcars[newN].end = cars[i].end;//接上        }        else if(cars[i].start >= newcars[newN].start and cars[i].end <= newcars[newN].end)            continue;//包含或相等关系 不进行任何操作        else{
   //如果没有在上一步把相等关系处理掉的话, 在此个else块里会造成问题            newN++;//无交集 建立新的片段            newcars[newN].start = cars[i].start;            newcars[newN].end = cars[i].end;        }    }    // cout<<"------"<
       
         maxIN )            maxIN = period;    }    //maxOUT    for (int i = 1; i <= newN; ++i)    {        int interval = newcars[i].start - newcars[i-1].end;        if( interval > maxOUT )            maxOUT = interval;    }       cout<
        
         <<" "<
         
          <