DP20 求pair的最大长度链 Maximum Length Chain of Pairs @geeksforgeeks

是LIS的变型题，如果遇到两维则先排序一维再对另一维动态规划

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number. A pair (c, d) can follow another pair (a, b) if b < c. Chain of pairs can be formed in this fashion. Find the longest chain which can be formed from a given set of pairs.
Source: Amazon Interview | Set 2

For example, if the given pairs are {{5, 24}, {39, 60}, {15, 28}, {27, 40}, {50, 90} }, then the longest chain that can be formed is of length 3, and the chain is {{5, 24}, {27, 40}, {50, 90}}

This problem is a variation of standard Longest Increasing Subsequence problem. Following is a simple two step process.
1) Sort given pairs in increasing order of first (or smaller) element.
2) Now run a modified LIS process where we compare the second element of already finalized LIS with the first element of new LIS being constructed.

The following code is a slight modification of method 2 of this post.

package DP;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class MaximumLengthChainOfPairs {

	public static void main(String[] args) {
		Pair p1 = new Pair(5, 24);
		Pair p2 = new Pair(39, 60);
		Pair p3 = new Pair(15, 28);
		Pair p4 = new Pair(27, 40);
		Pair p5 = new Pair(50, 90);
		Pair[] A = {p1,p2,p3,p4,p5};
		int n = A.length;
		System.out.println(maxChainLength(A, n));	// {{5, 24}, {27, 40}, {50, 90}}
	}
	
	public static int maxChainLength(Pair[] A, int n){
		Arrays.sort(A, new Comparator
  
   () {
			@Override
			public int compare(Pair o1, Pair o2) {
				return o1.a - o2.a;
			}
		});
		
//		System.out.println(Arrays.toString(A));
		
		int[] mcl = new int[n];
		int max = 0;
		
		/* Initialize MCL (max chain length) values for all indexes */
		for(int i=0; i
   
    
 
    
 
    
 
    
http://www.geeksforgeeks.org/dynamic-programming-set-20-maximum-length-chain-of-pairs/