马上要到考试周了，王炸发现自己平时光顾着去网吧学ACM了，功课还真没怎么复习。抛开数据结构这种送分的课程，还有一些例如大物、概率论这种费时费力的课程。王炸决定花上一些时间开始复习了。
根据考试安排，王炸发现自己有n门功课需要复习，对于每门功课，给出Si、Li（1 ≤ i ≤ n），分别表示复习该门课程的开始时间以及持续时间。但是王炸发现这些复习的时间段有重合部分，也就是说只凭自己本身是不能复习完所有功课的，但是这难不倒王炸，他从师父那里学到了一招————奥义·影分身，王炸可以让自己的分身和自己同时复习。但是释放影分身需要消耗相当大的能量，所以他想尽量少的释放影分身。
现在他请你帮他算一下他至少需要多少影分身才能复习完所有课程。
第一行一个整数T（1 ≤ T ≤ 50）表示一共T组数据
每一组数据的第一行有一个正整数n（1 ≤ n ≤ 10000），表示需要复习功课的数量。
接下来n行，每行两个数Si和Li（1 ≤ Si、Li ≤ 10^7），表示的意义如题目描述所示。
对于每组数据输出一个整数，表示最少需要的影分身的数量。
对于样例1，因为第2个时间点有重合，所以需要派出一个影分身去复习，所以应该输出1。
对于样例2，王炸自己学习功课3和2，派出一个影分身学习功课4和1，所以应该输出1
补充i点知识先 /* upper_bound() #include <iostream> #include <algorithm>//必须包含的头文件 using namespace std; int main(){ int point[10] = {1,3,7,7,9}; int tmp = upper_bound(point, point + 5, 7) - point;//按从小到大，7最多能插入数组point的哪个位置 printf("%d\n",tmp); tmp = lower_bound(point, point + 5, 7) - point;按从小到大，7最少能插入数组point的哪个位置 printf("%d\n",tmp); return 0; } output: 42*/
思路： 可以看出来 ，就是区间覆盖问题，但是一看时间都凌乱了。。 问了大神才 有的优化时间后的代码
每有一个开始，个数就要+1，每完成一件事情，个数就要-1； 所以要是在一个区间里一直有加的个数大于减的个数，就表明是 有重叠了、、、 在这期间一直更新max_num的个数就可以了。。。
代码
#include<string.h> #include<stdio.h> #include<algorithm> #include<math.h> #include<queue> #include<stack> #define inf 0x3f3f3f #define M 10000*2+10 #define LL long long using namespace std; int a[M]; int b[M]; int cmp(int x,int y) { return x<y; } int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); for(int i=0;i<n;i++) { int time; scanf("%d%d",&a[i],&time); // 记录 开始的点 b[i]=a[i]+time; // 记录 结束的点 } sort(a,a+n,cmp); //排序 sort(b,b+n,cmp); int max_num=-1; for(int i=0;i<n;) // 核心 { int k=upper_bound(a,a+n,a[i])-a; // 记录 a[i]这个点之前有几个开始的点 有几个开始加几 int l=upper_bound(b,b+n,a[i])-b-1;//a[i] 这个点之前有几个结束的点 有几个结束的点，就减几 i=k; if(max_num<k-l-1) max_num=k-l-1; } printf("%d\n",max_num-1); } return 0; }