POJ(PKU) 1065 Wooden Sticks

闇。

このブログを参考にさせていただきました。
http://d.hatena.ne.jp/atetubou/20110528/1306544909

以上。

#include <cstdio>
#include <algorithm>
#include <utility>

using namespace std;

int main(){
  
  int t;
  
  scanf("%d",&t);
  
  while(t--){
  
  int n;
  bool use[5003];
  int ans = 0;
  
  pair<int,int> d[5003];
  
  scanf("%d",&n);
  
  for(int i = 0;i < n;i++){
    scanf("%d%d",&d[i].first,&d[i].second);
    use[i] = false;
  }
  
  sort(d, d + n);
  
  int l = -1,w = -1;
  
  for(int i = 0;i < n;i++){
    if(use[i] == true) continue;
    
    if(l == -1){
      l = d[i].first;
      w = d[i].second;
      ans++;
      use[i] = true;
    }else{
      for(int j = i;j < n;j++){
	if(use[j])continue;
	if(l <= d[j].first && w <= d[j].second){
	  l = d[j].first;
	  w = d[j].second;
	  use[j] = true;
	}
      }
      l = -1,w = -1;
      i--;
      
    }
  }
  
  printf("%d\n",ans);
  
  }
  
  return 0;
  
}