# 0646. Maximum Length of Pair Chain
###### tags: `Leetcode` `Medium` `Greedy`
Link: https://leetcode.com/problems/maximum-length-of-pair-chain/
## 思路 $O(NlogN)$ $O(1)$
贪心算法
根据right pos排序
只要现在的pair的left比 之前的决定要拿的pair里面最大的right 大（不会重合），就把这个pair算进去
证明：optimal solution里面一定含有right pos最小的那个pair $i$
假设一个optimal solution $S'$，不含pair $i$，那么假设$S'$里面right pos最小的是pair $j$，那么可以用pair $i$替换掉pair $j$
## Code

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a,b)->(a[1]-b[1]));
        int ans = 0;
        int pre = Integer.MIN_VALUE;
        for(int[] pair:pairs){
            if(pre < pair[0]){
                ans++;
                pre = pair[1];
            }
        }        
        return ans;
    }
}