Leetcode解题报告——646. Maximum Length of Pair Chain

题目要求：
You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.

Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.

Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.

Example 1:
Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

题目大意：
在给定数组集中，找出能形成链状的子集，求其长度，这道题中，链状子集指前一个数组的第二位元素小于下一个数组的第一位元素

解题思路：
我们可以利用类似贪心算法分析此问题，若想子链越长，则每个节点的第二位元素尽可能小，所以我们维护一个最小堆，将数组集按数组的第二位元素从小到大排序，然后遍历每个节点，若符合链状结构，则将长度加1

代码示例：

public static int findLongestChain(int[][] pairs) {

       Comparator<int[]> comparator = new Comparator<int[]>() {
           @Override
           public int compare(int[] o1, int[] o2) {
               return o1[1]-o2[1];
           }
       };

       PriorityQueue<int[]> queue =new PriorityQueue<int[]>(pairs.length,comparator);
        for (int[] pair : pairs) {
            queue.add(pair);
        }
        int result = 1,max = queue.poll()[1];
        int k = queue.size();
        for (int i = 0; i < k; i++) {
            int []var = queue.poll();
            if(max < var[0]){
                max = var[1];
                result++;
            }
        }
        return result;
    }