越来越菜了
题解 #
贪心的策略是:遍历所有点,当我们发现有被超过条线段覆盖的点时,我们应该移除右端点最靠右的线段。
为了实现我们的策略,我们需要一个数组 来存储以点开始的线段,和数组来存储以点结束的线段。我们同时还需要维护覆盖当前点的集合,以及一个优先队列来寻找右端点最右的线段。
具体来说,就是对于每个点,我们先往集合里插入从这个点开始的线段,然后找出应该删除的线段并删除,最后从集合里移除以这个点结束的线段。
Code #
#include <bits/stdc++.h>
#define F first
#define S second
#define endl '\n'
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
const int N=2e5+5;
vector<pii> open[N];
vector<int> close[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
int l,r;
cin>>l>>r;
close[r].emplace_back(i);
open[l].emplace_back(r,i);
}
set<int> now;
vector<int> ans;
priority_queue<pii> pq;
for(int i=1;i<=N-1;i++){
for(auto it:open[i]){
now.insert(it.S);
pq.push(it);
}
while(now.size()>k){
pii tmp=pq.top();
pq.pop();
now.erase(tmp.S);
ans.emplace_back(tmp.S);
}
for(int x:close[i]){
now.erase(x);
}
}
cout<<ans.size()<<endl;
for(int it:ans) cout<<it<<' ';
return 0;
}