[代码元]#503. 工作安排

题目：

 分析：

时间是一秒一秒过的，而且任务也是一秒就可以完成，那么工作时长就是我们可以完成的任务了。

我们如果按照工作截止时间递增排序，对于我们的工作时间来说，如果当前任务还没有截止，那么我们就可以直接完成它，如果当前任务时间已经截至了，我们可以看一下前面完成的任务有没有价值比他低的，并替换掉。毕竟同样是在有限的时间内完成的任务，我们肯定要更贪心的选择价值更高的任务完成。这一操作可以使用小根堆的优先队列来实现。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

int n;
struct Node{
	int a, b;
	bool operator< (const Node &W) const{
		return a < W.a;
	}
}a[N];
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i ++ )
	{
		scanf("%d%d", &a[i].a, &a[i].b);	
	}	
	
	sort(a + 1, a + 1 + n);
	
	priority_queue<int , vector<int>, greater<int> > q;
	// 队列表示当前工作的时长 
	for (int i = 1; i <= n; i ++ )
	{
		int x = a[i].a, y = a[i].b;
		
		if (x <= 0) continue;
		if (x > q.size()) // 这个工作截止时间还没到 
		{
			q.push(y);
		}
		else if (x <= q.size()) // 这个工作已经截止了 
		{
			if (y > q.top()) // 这个工作的价值截止了，但是已经完成的其他工作来说，价值更高 
			{
				q.pop();
				q.push(y);
			}
		}
	 } 
	 
	 int res = 0;
	 while (q.size())
	 {
	 	res += q.top();
	 	q.pop();
	 	
	 }
	 cout << res << endl;
	 return 0;
}