PROBLEM C
CLASSROOMS
The new semester is about to begin, and finding classrooms for orientation activities is always a headache.
There are k classrooms on campus and n proposed activities that need to be assigned a venue. Every proposed activity has specfic starting time si and ending time fi. Any such an activity should take place at one of the classrooms. Any of the k classrooms is big enough to hold any of the proposed activities, and each classroom can hold at most one activity at any time. No two proposed activities can take place at the same classroom at the same time. Even if two proposed activities overlap momentarily (the ending time of one activity equals the starting time another activity), they cannot be assigned to the same classroom.
There are so many proposed activities that there may not be enough classrooms to hold all the activities. It is desirable to have as many activities as possible. At most how many proposed activities can be assigned to the classrooms?
Input
- The first line contains two positive integers n and k (1≤k≤n≤200000 ), representing the number of proposed activities and number of classrooms, respectively.
- The following n lines each contains two positive integers: the ith line among these n lines contains si and fi (1≤si≤fi≤109), indicating the starting time and ending time of proposed activity i
Output
Output an integer indicating the maximum number proposed activities that can be scheduled.
Sample Input 1
4 2
1 4
2 9
4 7
5 8
Sample Output 1
3
題意
題意渊鞋，n個活動，k個教室吕粗，給定每個活動開始和結(jié)束時間柳沙，在同一個教室舉行的連續(xù)兩個活動結(jié)束時間和開始時間之間必須有間隔坝茎。問最多能舉辦多少個活動惧眠。
貪心详囤，把每個活動按結(jié)束時間排序，然后從頭到尾掃一遍肋拔。
multiset里存放每個教室正在進行的活動的結(jié)束時間。
如果multiset里有某個教室的活動在活動i開始之前就結(jié)束的呀酸，活動i就可以舉辦凉蜂，把原來的結(jié)束時間刪掉，再把活動i的結(jié)束時間存進去性誉。
如果multiset里沒有比a[i].begin小的結(jié)束時間窿吩，即當前有活動的教室在活動i開始之前都結(jié)束不了活動，此時multiset里元素的數(shù)量表示有多少個教室在同時進行活動错览，如果還有空教室纫雁，活動i就可以在這個教室進行，把活動i的結(jié)束時間存入multiset倾哺。
注：實際存入multiset的是 (-a[i].ed-1),而查找時用的是（-a[i].begin）轧邪。因為要使用lower_bound函數(shù)，而lower_bound（start,end,k）返回的是集合里大于等于k的第一個數(shù)的下標羞海，而題目里面要查找的是 比 開始時間 小的 第一個 結(jié)束時間忌愚，加個負號就剛好。
#include <algorithm>
#include <iostream>
#include <set>
#define N 200005
using namespace std;
int n , k;
struct node{
int bg,ed;
}a[N];
bool cmp(node a , node b){ //sort-cmp
if(a.ed== b.ed) return a.bg < b.bg;
return a.ed< b.ed;
}
int main(){
cin >> n >> k;
for (int i = 0 ; i < n ; ++i)
cin >> a[i].bg >> a[i].ed;
sort(a,a+n,cmp); //按照結(jié)束時間排序
multiset<int> endtime;
//multiset存放每個教室正在進行的活動的結(jié)束時間
endtime.clear();
int ans = 0; //活動個數(shù)
for (int i = 0 ; i < n ; i++){ //遍歷每個活動
multiset<int> :: iterator iter;
iter = endtime.lower_bound(-a[i].bg);
//是否存在某個教室的活動在i開始時間前前就結(jié)束了
if (iter == endtime.end()){
//如果沒有在活動i開始前就結(jié)束活動的教室却邓，就另找一個教室
if (endtime.size() < k){
endtime.insert(-a[i].ed- 1);
ans++;
}
continue;
}
endtime.erase(iter);
//找到了某個教室活動已經(jīng)結(jié)束了硕糊，活動i在這個教室進行
endtime.insert( - a[i].ed - 1);
//更新活動的結(jié)束時間
ans++;
}
cout << ans << endl;
return 0;
}
