提交鏈接
http://codeforces.com/gym/100781/submit
Description：
Ada, Bertrand and Charles often argue over which TV shows to watch, and to avoid some of their fights they have finally decided to buy a video tape recorder. This fabulous, new device can record k different TV shows simultaneously, and whenever a show recorded in one the machine’s k slots ends, the machine is immediately ready to record another show in the same slot.
The three friends wonder how many TV shows they can record during one day. They provide you with the TV guide for today’s shows, and tell you the number of shows the machine can record simultaneously. How many shows can they record, using their recording machine? Count only shows that are recorded in their entirety.
Input
The first line of input contains two integers n, k (1 ≤ k < n ≤ 100 000). Then follow n lines, each containing two integers xi , yi , meaning that show i starts at time xi and finishes by time yi . This means that two shows i and j, where yi = xj , can be recorded, without conflict, in the same recording slot. You may assume that 0 ≤ xi < yi ≤ 1 000 000 000.
Output
The output should contain exactly one line with a single integer: the maximum number of full shows from the TV guide that can be recorded with the tape recorder.
Sample 1：
3 1
1 2
2 3
2 3
2
Sample 2：
4 1
1 3
4 6
7 8
2 5
3
Sample 3：
5 2
1 4
5 9
2 7
3 8
6 10
3
題意：輸入n，k 表示有n場電視節目，最多可以同時錄制k場，然後n行輸入電視節目的起始時間和結束時間，注意(x1,y1) (x2,y2) y1==x2 不算重疊，求能錄制的最多數量；
思路：定義多重集合 multiset<int>q; 插入k個0，表示同時錄制時已經錄制完部分電視節目的結束時間，把n個電視節目按結束時間排序，依次進行處理，如果當前電視節目的起始時間比集合中的k個數都要小，則表示當前節目不能放在k個節目任何一個節目後錄制，則跳過；否則，在k個結束時間中找一個小於等於（最接近的，貪心原則）當前節目開始時間的值，然後刪掉更新為當前節目的結束時間；
感悟：我做這道題時，一直沒往這個方向想，唉，太智障了~
代碼如下：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
struct Node
{
int s,e;
}node[100005];
bool cmp(const Node x,const Node y)
{
if(x.e==y.e) return x.s>y.s;
return x.e<y.e;
}
multiset<int>q;
multiset<int>::iterator it;
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
q.clear();
for(int i=0;i<n;i++)
scanf("%d%d",&node[i].s,&node[i].e);
sort(node,node+n,cmp);
for(int i=0;i<k;i++)
q.insert(0);
int sum=0;
for(int i=0;i<n;i++)
{
it=q.upper_bound(node[i].s);
if(it==q.begin()) continue;
it--;
q.erase(it);
q.insert(node[i].e);
sum++;
}
cout<<sum<<endl;
}
}
