nesteddolls.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 78 行

package PKU.GA;
import java.util.Arrays;
import java.util.Scanner;



/**
 * ID:3636
 * @author yhm
 *
 */
public class NestedDolls {

	static NestedDollsNode[] array;
	static int num;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int caseNum = cin.nextInt();
		for(int i=0;i<caseNum;i++){
			num = cin.nextInt();
			array = new NestedDollsNode[num];
			for(int j=0;j<num;j++){
				array[j] = new NestedDollsNode(cin.nextInt(),cin.nextInt());
			}
			Arrays.sort(array);
			solve();
			
		}

	}
	
	static void solve(){
		int sum=1;
		int[] max = new int[num+1];
		max[sum]=array[0].w;
		for(int i=1;i<num;i++){
			int w = array[i].w;
			boolean needNew=true;
			for(int j=1;j<=sum;j++){
				if(w>max[j]){
					max[j]=w;
					needNew=false;
					break;
				}
			}
			if(needNew){
				sum++;
				max[sum]=w;
			}
		}
		
		System.out.println(sum);
	}

}



class NestedDollsNode implements Comparable<NestedDollsNode>{
	public int compareTo(NestedDollsNode o) {
		if(l.compareTo(o.l)!=0){
			return l.compareTo(o.l);
		}
		else{
			return 0-w.compareTo(o.w);
		}
	}
	Integer l;
	Integer w;
	public NestedDollsNode(int l, int w) {
		super();
		this.l = l;
		this.w = w;
	}
}