带悔贪心 QOJ interval

interval

带反悔的贪心

即通过堆（大根堆、小根堆）来维护当前贪心策略的最优解，若发现最优解不对，就退回上一步，更新最优解。

将区间按照左端点排序，从左向右遍历区间。当前区间为 \([l,r]\)，取出当前右端点最左的区间，可以就匹配。

如果不可以，去看看已经匹配的这些对区间中的 \((b,c)\)，\(c\) 的右端点是否在 \(a\) 左侧，若是，则 \(a,b\) 匹配，\(c\) 放入未匹配的队列，因为右端点越左说明在后面匹配上的可能就越大。

反悔贪心就是我们维护一个反悔堆，把想要反悔的放到堆中，然后不断贪心，如果发现可以反悔（会使结果更优或可能更优），那就反悔。
反悔操作指的是这一步的贪心不是全局最优解，我们就退回去一步。

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline void read(T &x){
	x = 0;
	static char c;
	static bool f;
	c = getchar(), f = 0;
	while(c < '0' || c > '9'){ if(c == '-')f = 1; c = getchar(); }
	while('0' <= c && c <= '9')x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	x = f ? -x : x;
}
template <typename T,typename ...Types>
inline void read(T &x,Types &...y){
	read(x);
	read(y...);
}

const int N = 5e5 + 10;
using pii = pair<int,int>;
priority_queue<pii,vector<pii>,greater<pii> > a,b;
int n,ans[N],m;
int match[N],mp[N];
struct P{
	int l,r,id;
	bool friend operator <(const P &a,const P &b){
		return a.l == b.l ? a.r < b.r : a.l < b.l;
	}
}s[N];



int main(){
	read(n),read(m);
	for(int i = 1;i<=n;++i)read(s[i].l,s[i].r),s[i].id = i;
	sort(s+1,s+n+1);
	for(int i = 1;i<=n;++i){
		int l = s[i].l, r = s[i].r, id = s[i].id;
		mp[i] = id;
		if(a.size() && a.top().first < l){
			match[mp[a.top().second]] = id;
			match[id] = mp[a.top().second];
			a.pop(),b.push({r,i});
		}
		else if(b.size() && b.top().first < r){
			int to = match[mp[b.top().second]];
			match[to] = id, match[id] = to;
			match[mp[b.top().second]] = 0;
			a.push(b.top()),b.pop(),b.push({r,i});
		}
		else a.push({r,i});
	}
	int tot = 0;
	for(int i = 1;i<=n;++i){
		if(match[i]){
			ans[i] = ans[match[i]] = ++tot;
			match[match[i]] = 0;
		}
	}
	for(int i = 1;i<=n;++i){	
		(ans[i] == 0) && (ans[i] = ++tot);
		printf("%d ",ans[i] > m ? 0 : ans[i]);
	}
	return 0;
}