PKU 1065 Wooden Sticks

問題

n本の木の棒があり、それぞれの太さはw[i], 長さはl[i]である。
この木の棒を好きな順番で機械に入れていく。

最初の一本を入れるときには1のコストがかかる。
前の棒が(w[i], l[i])であるとき、次の棒(w'[i], l'[i])が
w[i]≦w'[i]かつl[i]≦l'[i]ならばコストがかからない。
そうでないならコストが1かかる。

適切な順序で棒を入れたとき、かかるコストの最小値を求めよ。

制約条件

n≦5000
w[i], l[i]≦10000

方針

DAGの最小パス被覆でやろうとしててTLEになってた。
二部グラフの最大マッチングの計算量はO(V(V + E))なので、どう考えても間に合わない。
（計算量をO(V^2)とかだと思ってた）

次のような貪欲法をすればいいとfura2さんのブログに書いてあった。

まず、wの昇順で棒を並べる。wが等しいときはlの昇順。
するとlだけを考えればいい。
lの今までにできた列の末尾を
l0 l1 l2 ...とすると、新しいlを列に加えるとき、
l≧liとなるようなliのうち最大のliをもつ列の末尾に加えればよい。

そのような列が存在しないとき、新しい列を作る。

ソースコード

int n;
pi p[5000];

int main()
{
	int cs;
	cin >> cs;
	while(cs--){
		
		map<int, int> m;
		cin >> n;
		rep(i, n) cin >> p[i].first >> p[i].second;
		
		sort(p, p + n);
		m[p[0].second]++;
		for(int i = 1; i < n; i++){
			map<int, int>::iterator it = m.upper_bound(p[i].second);
			it--;
			
			if(it ->first <= p[i].second){
				if(--it->second == 0) m.erase(it);
			}
			m[p[i].second]++;
		}
		cout << m.size() << endl;
	}
	return 0;
}