Nested Dolls

You're gonna need to take a look here Online Algorithms for Dilworth's Chain Partition and here Dilworth's theorem, and I think you will get it...

http://ncpc.idi.ntnu.no/ncpc2007/ncpc2007solutions.pdf

Find The Longest Decreasing Subsequence But keep in mind that you can take 2 equal values like 3 3 2 2 1 1 is a valid decreasing subsequence

It is my solution :
Prerequisite : range tree
MAXN = 1000 highest value of width and height
T[1000] is array and all elemnt of T is zero
query(x, 1, MAXN, 1) = find the biggest number which is small or equal to x
upd(x, y, 1, MAXN, 1) is T[x] = y;

    scanf("%d",&n);

    for(int h=0; h<n; h++)
    {
       int a, b;
       scanf("%d %d",&a,&b);
       D[a].push_back(b);
    }

    for(int h=1; h<=MAXN; h++)
    {
       for(int j=0; j<(int)D[h].size(); j++)
       {
         int k = query(D[h][j]-1, 1, MAXN, 1);

         L[k]--;

         if(!L[k])    upd(k, 0, 1, MAXN, 1);
       }

       for(int j=0; j<(int)D[h].size(); j++) upd(D[h][j], D[h][j], 1, MAXN, 1),L[D[h][j]]++;
    }

    for(int h=1; h<=MAXN; h++) ans += L[h];

    printf("%d\n",ans);

my greedy approach