ZOJ 3508 The War（贪心）

题目链接：Click here~~

题意：

有N个区间，M个点，问怎样使得更多的区间满足包含且仅包含一点（不能重复包含）。

解题思路：

貌似是区间选点问题的变形。

假设区间左右端点为a,b，按照b从小到大排序，如果b相同按照a从大到小排序，即满足小区间在前。

策略是：首先满足前面的区间，并取该区间中第一个满足条件的点（即最小的点）。

不妨设排序后的任意两个相邻区间为A,B，且A在B之前。

1、如果B区间包含A区间，那么取A区间中最小的点不会使结果更差，因为B区间的范围比A区间大，可选择余地也多，能选到其他点的机会更大。

而如果让B区间选择此点的话，A区间可选择范围会变得更小，而且可能会浪费掉B区间在A区间之外的点。

2、如果B区间不包含A区间，那么有Aa<Ba。取A区间中最小的点还是会使后面的选择更有利。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

struct Extent
{
    int a,b;
    bool operator < (const Extent& S) const
    {
        return b == S.b ? a > S.a : b < S.b;
    }
}A[2505];

int num[1005];

int main()
{
    int n,m,t;
    while(~scanf("%d%d",&n,&m))
    {
        memset(num,0,sizeof(num));
        int ans = 0;
        for(int i=0;i<n;i++)
            scanf("%d%d",&A[i].a,&A[i].b);
        while(m--)
        {
            scanf("%d",&t);
            ++num[t];
        }
        sort(A,A+n);
        for(int i=0;i<n;i++)
            for(int j=A[i].a;j<=A[i].b;j++)
                if(num[j])
                {
                    ++ans;
                    --num[j];
                    break;
                }
        printf("%d\n",ans);
    }
    return 0;
}