pzhu~1084 值班时间

逃离我推掉我的手 2024-02-17 21:39 17阅读 0赞

### 值班时间 ###

### Description ###

假设学校某部门需要24小时不间断的有人值守，该部门有n名教师，同时考虑到有些老师还需要上课，所以学校允许他们实行弹性上班制。考虑到部门的运转，学校要求该部门任意时刻至少要有一个人在岗，但总有那么一些人会偷懒，如果给出你该部门有n（不超过5\*10^3）名教师，同时给出每名教师的上班时间和离开时间（为了好计算，假设时间我们都统一用秒来表示，且不大于10^6），让你计算出该部门有人值守的最长时间和无人值守的最长时间。(只考虑所有给出的时间中最大时间和最小时间这一段时间，其它时间段不用考虑，不要被24小时所干扰。)

### Input ###

第一行输入该部门总共有n名教师

下面n行依次分别输入n名教师的上班时间和离开时间。

### Output ###

输出该部门有人值守的最长时间和无人值守的最长时间。

### Sample Input ###

5  
800 1300  
1200 1600  
900 2000  
2100 2500  
3000 4000  
3  
100 200  
201 300  
250 500

### Sample Output ###

1200 500  
299 1

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=5e3+10;
    struct node{
    	int s,t;
    }nt[maxn];
    
    int YR,WR;
    
    bool cmp(const node& n1,const node& n2){
    	return n1.s<n2.s || (n1.s==n2.s&&n1.t<n2.t);
    }
    
    int main(){
    	int n;
    	while(scanf("%d",&n)==1){
    		for(int i=0;i<n;i++){
    			scanf("%d%d",&nt[i].s,&nt[i].t);
    		}
    		
    		sort(nt,nt+n,cmp);
    		YR=WR=0;
    		int s1=nt[0].t-nt[0].s,t1=0;
    		int end=nt[0].t;
    		
    		for(int i=1;i<n;i++){
    			WR=max(WR,t1);			
    			if(nt[i].s<=end){
    				if(nt[i].t>end){
    					s1+=nt[i].t-end;
    					end=nt[i].t;
    				}
    			}
    			else {
    				YR=max(YR,s1);
    				s1=nt[i].t-nt[i].s;
    				
                    YR=max(YR,s1);
    				
    				t1=nt[i].s-end;
    				end=nt[i].t;
    			}
    		}
    		
    		WR=max(t1,WR);
    		YR=max(s1,YR);
    		printf("%d %d\n",YR,WR);
    	}
    	return 0;
    }