Dowemo

Schedule Time limit: 4000/2000 ms ( java/others ) memory limit: 153428/153428 k ( java/others )
Total submission ( s ): 1069 accepted submission ( s ): 436


Problem description there are n schedules, the i-th schedule has start time si and end time ei( 1 <= I <= n ). There are some machine. Each two overlapping schedules cannot be the = same. timeend and timestart where time_ % 7bend % 7d is time to turn off the machine timestartA is time to turn on the machine. We assume that the machine cannot be. timestart and the timeend.
Print the minimum number k of the for performing all schedules, and when g. G. Machines, print the minimum sum of.
Input the first line contains an integer t ( 1 <= t <= 100 ); the number of test cases. Each. si and ei ( 0 < = si< ei< = 1 e9 ) .
Output for each test case, print the minimum possible number of machine and the minimum sum of all.
Sample Input

1


3


1 3


4 6


2 5






Sample Output

2 8






Source 2017 multi-university training contest - team 10
A recommend liuyiding | we've carefully selected several similar problems for you: 6181 6180 6179 6177
Policy is greedy. Select update if the start time of the work you're joining is greater than the end time of a work that has already been joined. Otherwise, add new work to the set container. Use upper bound function to handle.

#include <iostream>


#include <ctime>


#include <cstring>


#include <set>


#include <algorithm>


using namespace std;



const int maxn = 1e5+5;


struct node{


 int s,e;


 node() {}


 node (int x, int y) {s=x; e=y;}


 bool operator <(const node &x) const{


 return e<x.e;


 }


}p[maxn];


int i,j,k,n,T;


long long cnt,ans;


multiset <node>s;


multiset <node>::iterator it;



bool cmp(node a, node b){


 if (a.s!=b.s) return a.s<b.s;


 return a.e<b.e;


}



void init(){


 cin>> n;


 for (i=0; i<n; i++ ) cin>> p[i].s>> p[i].e;


 sort(p,p+n,cmp);


 s.clear();


 s.insert(p[0]);


}



int main(){


 std::ios::sync_with_stdio(false);


 cin>> T;


 node a,b;


 int x;


 while (T--) {


 init();


 for (i=1; i<n; i++) {


 a = node(0,p[i].s);


 it = s.upper_bound(a);


 if (it!=s.begin()) {//表明it前一个工作的结束时间一定小于当前工作的开始时间


//更新节点


 it--;


 x = it->s;


 s.erase(it);


 b = node(x,p[i].e);


 s.insert(b);


 }


 else s.insert(p[i]);


 }


 ans = 0;


 cnt = s.size();


 for (it = s.begin(); it!=s.end(); it++) ans += it->e - it->s;


 cout <<cnt <<"" <<ans <<endl;


 }


 return 0;


}











Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs