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
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