贪心

贪心

贪心算法（Greedy Algorithm）是一种基于逐步构建解决方案的算法设计思想。它在每一步选择中，都采取当前状态下的局部最优解，以期最终得到问题的全局最优解。贪心算法通常用于解决优化问题，例如最小生成树、最短路径问题和活动选择问题等。

经典问题

井然有序之窗

https://ac.nowcoder.com/acm/contest/95323/H

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

struct space {
	int l;
	int r;
	// 记录每个区间的序号
	int id;
};

// 按左边界升序排序，若相等按右边界升序排序
bool cmp1 (space a, space b) {
	if (a.l != b.l) return a.l < b.l;
	return a.r < b.r;
}

// 对结构体使用优先队列，找到每个结构体中最小的 r，所以使用小根堆
struct cmp2{
	bool operator()(const space& a, const space& b) {
		return a.r > b.r;  
	}
};

void solve()
{
	// 贪心思想	
	int n;
	cin >> n;
	vector<space> s(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> s[i].l >> s[i].r;
		s[i].id = i;
	}
	sort(s.begin() + 1, s.end(), cmp1);
	// 使用结构体按 r 排序
	priority_queue<space, vector<space>, cmp2> pq;
	vector<int> ans;
	map<int, int> cnt;
	// 每次找到右边界最小的区间，处理完之后还要删去已经不符合要求的区间
	for (int i = 1, j = 1; i <= n; i++) {
		while (s[j].l == i && j <= n) {
			pq.push(s[j]);
			j++;
		}
		if (!pq.empty()) {
			ans.push_back(pq.top().id);
			pq.pop();
		}
		// 判断是否为空要写在前面
		while (!pq.empty() && pq.top().r == i) {
			pq.pop();
		}
	}
	if (ans.size() == n) {
		// 最后找到了在符合1 2 3 4 5 6 7要求下的
		// 区间序号1 6 5 3 2 7 4
		// 用map即可实现将1 2 3 4 5 6 7按照1 6 5 3 2 7 4的顺序输出
		for (int i = 0; i < ans.size(); i++) {
			cnt[ans[i]] = i + 1;
		}
		for (auto x : cnt) {
			cout << x.second << " ";
		}
		cout << endl;
	} else {
		cout << -1 << endl;
	}
	
	cout << endl;
} 

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}