テスト試合D-The War(コントロール範囲のある欲張り)

D - The War
Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu
Submit
 
Status
Description
A war had broken out because a sheep from your kingdom ate some grasses which belong to your neighboring kingdom. The counselor of your kingdom had to get prepared for this war. There are N (1 <= N <= 2500) unarmed soldier in your kingdom and there are M (1 <= M <= 40000) weapons in your arsenal. Each weapon has a weight W (1 <= W <= 1000), and for soldier i, he can only arm the weapon whose weight is between minWi and maxWi ( 1 <= minWi <= maxWi <= 1000). More armed soldier means higher success rate of this war, so the counselor wants to know the maximal armed soldier he can get, can you help him to win this war?
Input
There multiple test cases. The first line of each case are two integers N, M. Then the following N lines, each line contain two integers minWi, maxWi for each soldier. Next M lines, each line contain one integer W represents the weight of each weapon.
Output
For each case, output one integer represents the maximal number of armed soldier you can get.
Sample Input

3 3
1 5
3 7
5 10
4
8
9
2 2
5 10
10 20
4
21

Sample Output

2
0

貪欲な問題、人が使うことができるいくつかの範囲があって、武器は重量があって、唯一解決しなければならない問題は一人のコントロールの範囲内で別の人を含んで、このような情況は範囲の小さい先を探します
yは小さいから大きいまであり、yが同じであればxは小さいから大きいまである.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node{
    int x , y ;
} p[2600];
int q[1200] ;
bool cmp(node a,node b)
{
    return a.y < b.y || ( a.y == b.y && a.x < b.x ) ;
}
int main()
{
    int i , j , n , m ;
    while(scanf("%d %d", &n, &m) !=EOF )
    {
        memset(q,0,sizeof(q));
        for(i = 0 ; i < n ; i++)
            scanf("%d %d", &p[i].x, &p[i].y);
        while(m--)
        {
            scanf("%d", &i);
            q[i]++ ;
        }
        m = 0 ;
        sort(p,p+n,cmp);
        for(i = 0 ; i < n ; i++)
        {
            int l = p[i].x , r = p[i].y ;
            for(j = l ; j <= r ; j++)
                if( q[j] )
            {
                q[j]--;
                m++ ;
                break;
            }
        }
        printf("%d
", m);
    }
    return 0 ;
}