这题有点贪心的思想,将有交集的区间合并,然后求最长连续时间和最长不连续时间就可以了。。
我们先将区间按照起始时间从小到大的时间排序,假设(a,b)和(c,d),如果c在(a,b)内,则区间长度可以更新为(a,max(b,d)).如果不在(a,b)区间,
则c-b为不连续时间,并一直往下更新。。
#include <iostream> #include <algorithm> #include <string> #include <cstdio> #include <cstring> using namespace std; const int INF = 0x7f7f7f7f; struct T { int sat,ed; }p[5010]; bool cmp(T a,T b) { if(a.sat!=b.sat) return a.sat<b.sat; return a.ed<b.ed; } int main() { int n,i; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d%d",&p[i].sat,&p[i].ed); sort(p,p+n,cmp); int sat=p[0].sat,ed=p[0].ed; int preed=0; int maxxa=ed-sat,maxxb=0; for(i=1;i<n;i++) { if(p[i].sat>=sat&&p[i].sat<=ed) { if(p[i].ed>ed) ed=p[i].ed; } else { preed=ed; maxxa=max(maxxa,ed-sat); sat=p[i].sat; ed=p[i].ed; maxxb=max(maxxb,sat-preed); } } printf("%d %d\n",maxxa,maxxb); return 0; }