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 = ; i < n; i++)

            cin >> p[i].st >> p[i].en;

        sort(p, p + n, cmd);

        for (int i = ; i < k; i++)

            s.insert();

        int ans = ;

        for (int i = ; 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 ;

}