Entertainment Box Gym100781E(数据结构+贪心)

Entertainment Box

题意：

• 有n个节目，每个节目给出开始时间(st)和结束时间(en)；
• 有k个内存条这k个内存条可以同时存储节目。如果节目j的开始时间stj  大于等于节目i的结束时间，就可以放进内存条中；
• 问这k个内存条最多可以存储多少个节目。

思路：开一个multiset容器，开始压入k个0，表示k个内存条，这k个数表示存入的该内存条的最后一个节目的结束时间。将所有的节目按结束时间由小到大排序，然后遍历所有节目的开始时间，查找最后一个小于等于当前开始时间的结束时间，更新，记录存起来的节目的数量。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
const int maxn = 1e5;
typedef long long ll;
//typedef pair<int,int> P;
struct P
{
    int st, en;
}p[maxn];
int n, k;
multiset<int> s;
multiset<int>::iterator it;
bool cmd(P &a, P &b)
{
    return a.en < b.en;
}

int main()
{
    while (cin >> n >> k)
    {
        s.clear();
        for (int i = 0; i < n; i++)
            cin >> p[i].st >> p[i].en;

        sort(p, p + n, cmd);

        for (int i = 0; i < k; i++)
            s.insert(0);

        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            it = s.upper_bound(p[i].st);
            if (it == s.begin()) continue;
            it--;
            s.erase(it);///更新节目的结束时间
            s.insert(p[i].en);
            ans++;
        }

        cout << ans << endl;
    }
    return 0;
}