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

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;



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;





int main(){


 cin>> T;

 node a,b;

 int x;

 while (T--) {


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

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

 it = s.upper_bound(a);

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



 x = it->s;


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



 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