POJ - 3614 Sunscreen区间选点问题（多个点）

题目大意

给定n个区间， m个值的点，每个值对应的点可以多个
问 每个区间匹配一个点 最多可以匹配多少个

样例

Sample Input
3 2
3 10
2 5
1 5
6 2
4 1
Sample Output
2

思路

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 3000;

struct node{
	int Min, Max;
	bool operator<(const node &a) const {
		return Min > a.Min;
	}
};
node spf[N];
int n, m;
int cover[N];

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		spf[i].Min = x;
		spf[i].Max = y;
	}
	for(int i = 1; i <= m; i++)
	{
		int s, c;
		scanf("%d%d", &s, &c);
		cover[s] += c;
	}
	sort(spf + 1, spf + 1 + n);
	int ans = 0;
	for(int i = 1; i <= n; i++)
	{	
		int l = spf[i].Min;
		int r = spf[i].Max;
		for(int j = r; j >= l; j--)
		{
			if(cover[j] > 0)
			{
				cover[j]--;
				ans++;
				break;
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}