题目链接
题意:
给定 N 项任务的起至时间( S1, E1 ), ( S2, E2 ), ..., ( SN, EN )， 计算最少需要多少台机器才能按时完成所有任务。
同一时间一台机器上最多进行一项任务，并且一项任务必须从头到尾保持在一台机器上进行。任务切换不需要时间。
思路:
这个题的话想明白了就是一个水题,这个题感觉类似于那种区间求差和区间求并集的问题,我们将所有的区间
记录虾左右端点然后放在同一个数轴上,需要特别注意的就是当某一个区间的左端点等于某个区间的右端点,应将右端点放
在左端点前面以保证所消耗的机器数最小。然后用sum记录空闲的机器数，扫一遍即可.
#include<bits/stdc++.h> #define Ri(a) scanf("%d", &a) #define Rl(a) scanf("%lld", &a) #define Rf(a) scanf("%lf", &a) #define Rs(a) scanf("%s", a) #define Pi(a) printf("%d\n", (a)) #define Pf(a) printf("%lf\n", (a)) #define Pl(a) printf("%lld\n", (a)) #define Ps(a) printf("%s\n", (a)) #define W(a) while(a--) #define CLR(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define inf 0x3f3f3f3f #define exp 0.00000001 #define pii pair<int, int> #define mp make_pair #define pb push_back using namespace std; typedef long long ll; const int maxn=1e5+10; struct node { int num; int flag; } q[maxn*2]; ll a[2*maxn]; int n; map<int,int>mpp; bool cmp(node a,node b) { if(a.num==b.num) return a.flag>b.flag; return a.num<b.num; } int main() { Ri(n); for(int i=1;i<=2*n;i+=2) { Ri(a[i]); q[i].num=a[i]; q[i].flag=1; Ri(a[i+1]); q[i+1].num=a[i+1]; q[i+1].flag=2; } ll s=1; /*mpp.clear(); sort(a+1,a+1+2*n); for(int i=1;i<=2*n;i++) { if(mpp[a[i]]==0) mpp[a[i]]=s++; } */ sort(q+1,q+1+2*n,cmp); int sum1=0,sum2=0,cnt=0; for(int i=1;i<=2*n;i++) { if(q[i].flag==1) { if(sum2==0) { cnt++; } else { sum2--; } //sum1++; } if(q[i].flag==2) { sum2++; } } Pi(cnt); return 0; } Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
