Dowemo
0 0 0 0

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< =1e9) .
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