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 machines. Each two overlapping schedules cannot be performed in the same machine. For each machine the working time is defined as the difference between
timeend
and
timestart
, where time_{end} is time to turn off the machine and
timestart
is time to turn on the machine. We assume that the machine cannot be turned off between the
timestart
and the
timeend
.
Print the minimum number K of the machines for performing all schedules, and when only uses K machines, print the minimum sum of all working times.
Input
The first line contains an integer T (1 <= T <= 100), the number of test cases. Each case begins with a line containing one integer N (0 < N <= 100000). Each of the next N lines contains two integers
si
and
ei
(0<=si<ei<=1e9)
.
Output
For each test case, print the minimum possible number of machines and the minimum sum of all working times.
Sample Input
1
3
1 3
4 6
2 5
Sample Output
2 8
Source
2017 Multi-University Training Contest - Team 10
Recommend
liuyiding | We have carefully selected several similar problems for you:
6181
6180
6179
6178
6177
策略是贪心。
如果当前要加入的工作的开始时间大于某个已经加入的工作的结束时间，就选择更新。
否则就添加新的工作进入set容器中。
使用upper_bound函数处理。
#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;
}
