Schedule

http://acm.hdu.edu.cn/showproblem.php?pid=6180

题意：已知一些任务的开始时间和结束时间，一台机器同时只能运行一个任务（机器中间不关闭运行），求在使用最少机器工作的前提下机器工作的最短时间

题解： 将开始时间标记为1，结束时间标记为-1。 
按照时间大小对这2n2n个时间从小到大排序，然后遍历计算前缀和，当前缀和每次增加1的时候，说明需要新开一台机器才能运行，这样可以寻找到每台机器的开始时间。同理，逆序遍历计算前缀和，可以记录下每一台机器的结束时间。最后把每一台机器的时间相加即可。
参考文章：原博客 简化版

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,u,v;
ll ans,cnt,flag,temp,sum;
int L[N],R[N];
char str;
struct node{
    int val,flag;
    bool operator <(const node &S)const{
        if(val==S.val)
            return flag<S.flag;
        return val<S.val;
    }
}e[N];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        for(int i=1;i<=n;i++){
            scanf("%d%d",&e[2*i-1].val,&e[2*i].val);
            e[2*i-1].flag=1;e[2*i].flag=-1;
        }
        n<<=1;
        sort(e+1,e+n+1);
        ans=0;
        k=0;
        for(int i=1;i<=n;i++){
            k+=e[i].flag;
            if(ans<k){
                ans=k;
                L[k]=e[i].val;
            }
        }
        ans=0;
        k=0;
        for(int i=n;i>=1;i--){
            k-=e[i].flag;
            if(ans<k){
                ans=k;
                R[k]=e[i].val;
            }
        }
        sum=0;
        for(int i=1;i<=ans;i++)
            sum+=R[i]-L[i];
        cout<<ans<<" "<<sum<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

#include<iostream>
#include<deque>
#include<memory.h>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<list>
#include<queue>
#include<set>
#define INF (1LL<<62)
#define ll long long int
using namespace std;
 
//输入挂，不然超时
int Scan(){
    int res = 0, flag = 0;
    char ch;
    if ((ch = getchar()) == '-'){
        flag = 1;
    }
    else if(ch >= '0' && ch <= '9'){
        res = ch - '0';
    }
    while ((ch = getchar()) >= '0' && ch <= '9'){
        res = res * 10 + (ch - '0');
    }
    return flag ? -res : res;
}
 
 
struct qujian{
    int l;
    int r;
    
}qs[100005];
 
bool cmp(qujian a,qujian b){
    return a.l<b.l;//按照开始时间排序
}
 
multiset<int> s; //一定要定义在外面，不然超时
 
int N;
 
int main()
{
    int t=Scan();
    while(t--){
        
        N=Scan();
        
        for(int i=0;i<N;i++){
            qs[i].l=Scan();
            qs[i].r=Scan();
        }
        
        sort(qs,qs+N,cmp);
        
        ll ans=0;
        
        s.clear();//s存所有机器的结束时间
        
        
        for(int i=0;i<N;i++){
            
            
            
            // multiset<int>::iterator it=upper_bound(s.begin(),s.end(),qs[i].l);//algorithm的二分超时！要用Set自带的
            multiset<int>::iterator it=s.upper_bound(qs[i].l);
            
            
            if(it==s.begin())//如果比所有都要小，那么只能新开一个机器了
            {
                
                ans+=qs[i].r-qs[i].l;//记录答案
                s.insert(qs[i].r);
            }
            else{
                it--;//细节
                
                //要把这两句合并，不然超时！这就是传说中的卡常数吗
                
                //   ans+=qs[i].l-*it;//空隙部分
                //  ans+=qs[i].r-qs[i].l;//当前工作的时间
                
                ans+=qs[i].r-*it;
                
                s.erase(it);
                s.insert(qs[i].r);
            }
        }
        
        
        printf("%d %I64d\n",s.size(),ans);
        
        
    }
    return 0;
}
 
 
 
 
 
 
 
 

C++版本三

#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define debug
using namespace std;
typedef long long LL;
const int maxn=200000+50;
struct Node
{
    LL x;
    int id;
    Node() {}
    Node(LL x,int id):x(x),id(id) {}
};
LL sum;;
stack<LL> s;
Node a[maxn];
int ans,n,num,cnt;
int cmp(Node a,Node b)
{
    if(a.x==b.x) return a.id>b.id;
    else return a.x<b.x;
}
void init()
{
    ans=0,sum=0,num=0,cnt=0;
    while(!s.empty()) s.pop();
}
int main()
{
#ifdef debu
    freopen("1010.in","r",stdin);
#endif // debug
    int t;
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d",&n);
        for(int i=0; i<n; i++)
        {
            LL l,r;
            scanf("%lld%lld",&l,&r);
            a[cnt++]=Node(l,0);
            a[cnt++]=Node(r,1);
            sum+=r-l;
        }
        sort(a,a+cnt,cmp);
        for(int i=0; i<cnt; i++)
        {
            if(a[i].id==0)
            {
                num++;
                if(!s.empty())
                {
                    LL pre=s.top();
                    s.pop();
                    sum+=a[i].x-pre;
                }
            }
            else
            {
                num--;
                s.push(a[i].x);
            }
            ans=max(ans,num);
        }
        printf("%d %lld\n",ans,sum);
    }
    return 0;
}