package com.fishercoder.solutions;

import java.util.Arrays;

public class _646 {

    public static class Solution1 {
        /**
         * credit: https://discuss.leetcode.com/topic/96804/java-o-nlog-n-time-o-1-space
         */
        public int findLongestChain(int[][] pairs) {
            Arrays.sort(pairs, (o1, o2) -> o1[1] - o2[1]);
            int result = 0;
            int n = pairs.length;
            int i = -1;
            while (++i < n) {
                result++;
                int curEnd = pairs[i][1];
                while (i + 1 < n && pairs[i + 1][0] <= curEnd) {
                    /**This means, we'll keep incrementing i until pairs[i+1][0] is
                     * exactly greater than curEnd.*/
                    i++;
                }
            }
            return result;
        }
    }

}
@@ -825,9 +825,751 @@
 %0A    %7D%0A%0A
+    public static class Solution2 %7B%0A        /**%0A         * credit: https://leetcode.com/problems/maximum-length-of-pair-chain/discuss/105623/Java-Very-Simple-without-DP%0A         */%0A        public int findLongestChain(int%5B%5D%5B%5D pairs) %7B%0A            Arrays.sort(pairs, (a, b) -%3E a%5B0%5D - b%5B0%5D);%0A            int len = 0;%0A            int pre = Integer.MIN_VALUE;%0A            for (int%5B%5D pair : pairs) %7B%0A                if (pair%5B0%5D %3E pre) %7B%0A                    //not overlap%0A                    len++;%0A                    pre = pair%5B1%5D;%0A                %7D else if (pair%5B1%5D %3C pre) %7B%0A                    //overlap but with a smaller second number%0A                    pre = pair%5B1%5D;%0A                %7D%0A            %7D%0A            return len;%0A        %7D%0A    %7D%0A%0A
 %7D

refactor 646