LeetCode 646 - Maximum Length of Pair Chain

https://leetcode.com/problems/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]

Note:

1. The number of given pairs will be in the range [1, 1000].

X. Interval + Greedy
https://leetcode.com/articles/maximum-length-of-pair-chain/

We can greedily add to our chain. Choosing the next addition to be the one with the lowest second coordinate is at least better than a choice with a larger second coordinate.

Consider the pairs in increasing order of their second coordinate. We'll try to add them to our chain. If we can, by the above argument we know that it is correct to do so.

• Time Complexity: $O(N \log N)$ where $N$ is the length of S. The complexity comes from the sorting step, but the rest of the solution does linear work.
• Space Complexity: $O(N)$. The additional space complexity of storing cur and ans, but sorting uses $O(N)$ space. Depending on the implementation of the language used, sorting can sometimes use less space.

https://discuss.leetcode.com/topic/96804/java-o-nlog-n-time-o-1-space

    public int findLongestChain(int[][] pairs)
    {
        Arrays.sort(pairs, (p1,p2)->p1[1]-p2[1] );

        int count = 0, end = Integer.MIN_VALUE;
        for (int[] pair : pairs)
        {
            if (pair[0] > end)
            {
                count++;
                end = pair[1];
            }
        }
        return count;
    }

http://www.voidcn.com/article/p-xeczbrwi-bmq.html
如果想使用Greedy来解决这个问题，那么只能是按照数组的第二个元素排序。(按照数组的第一个元素排序将会行不通）。如 (8,9) (10,11) (1,100)。
按照数组第一个元素排序： (1,100)，(8,9)， (10,11) 。不能通过比较 [i][end] 和 [i+1][begin] 来增加链。
而如果按照数组第二个元素排序： (8,9) ，(10,11)， (1,100)，那么则可以通过比较 [i][end] 和 [i+1][begin] 来增加链。

X. This is equivalent to interval scheduling problem.
https://blog.csdn.net/MebiuW/article/details/76284296
http://www.voidcn.com/article/p-duejwryb-bro.html

题目分析：经典的贪心问题，按照第二个数字对数组排序，然后按题意尽可能多的取即可，原因很简单，要保证后面尽可能多的取，那么前面也应该尽可能早的结束

因为要找最长的链，所以我们按照结尾的那个数字排序，这样可以尽量的最长
然后从第一个开始，直接往后遍历找就好，反正在前面的一定是一个最优解（因为不要求区间覆盖的覆盖长度，而是要求pair的数量）

相对的，如果是要找区间最长，应该就是排序后要上DP了，而不是这样直接找

public int findLongestChain(int[][] pairs) {
    Arrays.sort(pairs, (a,b) -> a[1] - b[1]);
    int sum = 0, n = pairs.length, i = -1;
    while (++i < n) {
        sum++;
        int curEnd = pairs[i][1];
        while (i+1 < n && pairs[i+1][0] <= curEnd) i++;
    }
    return sum;
}

http://fisherlei.blogspot.com/2017/07/leetcode-maximum-length-of-pair-chain.html
按照数组的结束数字排序，然后从左到右扫描。如果满足b<c的条件，则count+1.

1:    int findLongestChain(vector<vector<int>>& pairs) {  
2:      if(pairs.size() == 0) return 0;  
3:        
4:      std::sort(pairs.begin(), pairs.end(), comp);  
5:        
6:      int count = 1;  
7:      vector<int>& pair = pairs[0];  
8:      for(int i =1; i<pairs.size(); i++) {  
9:        if(pairs[i][0] > pair[1]) {  
10:          count ++;  
11:          pair = pairs[i];  
12:        }  
13:      }  
14:        
15:      return count;  
16:    }  
17:      
18:    static bool comp(vector<int>& a, vector<int>& b) {  
19:      return a[1] < b[1];  
20:    } 

http://blog.csdn.net/u014688145/article/details/75911369

此题还可以更优，时间复杂度为O(nlogn)，先对start排序，直接按照贪心法会出错，如：[1,20],[2,3],[4,5]，所以可以对end进行排序，于是有了[2,3],[4,5],[1,20]，此时再根据贪心选择start > end的区间，再更新end，即能得到答案。

public int findLongestChain(int[][] pairs) { int n = pairs.length; Arrays.sort(pairs, (a, b) -> a[1] - b[1]); int ans = 0; int end = Integer.MIN_VALUE; for (int i = 0; i < n; ++i){ while (i < n && pairs[i][0] <= end){ i ++; } if (i < n){ end = pairs[i][1]; ans ++; } } return ans; }

X. Stack
http://www.cnblogs.com/grandyang/p/7381633.html
这道题给了我们一些链对，规定了如果后面链对的首元素大于前链对的末元素，那么这两个链对就可以链起来，问我们最大能链多少个。那么我们想，由于规定了链对的首元素一定小于尾元素，我们需要比较的是某个链表的首元素和另一个链表的尾元素之间的关系，如果整个链对数组是无序的，那么就很麻烦，所以我们需要做的是首先对链对数组进行排序，按链对的尾元素进行排序，小的放前面。这样我们就可以利用Greedy算法进行求解了。我们可以用一个栈，先将第一个链对压入栈，然后对于后面遍历到的每一个链对，我们看其首元素是否大于栈顶链对的尾元素，如果大于的话，就将当前链对压入栈，这样最后我们返回栈中元素的个数即可

    int findLongestChain(vector<vector<int>>& pairs) {
        stack<vector<int>> st;
        sort(pairs.begin(), pairs.end(), [](vector<int>& a, vector<int>& b) {
            return a[1] < b[1];
        });
        for (auto pair : pairs) {
            if (st.empty()) st.push(pair);
            else {
                auto t = st.top();
                if (pair[0] > t[1]) st.push(pair);
            }
        }
        return st.size();
    }

我们可以对上面解法的空间进行优化，并不需要用栈来记录最长链上的每一个链对。而是用一个变量end来记录当前比较到的尾元素的值，初始化为最小值，然后遍历的时候，如果当前链对的首元素大于end，那么结果res自增1，end更新为当前链对的尾元素
X.
https://discuss.leetcode.com/topic/96799/java-memoization-solution-with-explanation-o-nlogn-solution

Sort the array, then find the longest chain starting at each array index from left to right. Imp thing is to make sure we call chain for each array index and not just the first one. As it might be the 1st one can have a very big b value.
Suppose we have [1,20],[2,3],[4,5]. If we simply take the chain value starting from the 1st index (chain:[1,20]) we get 1.
But if we take the chain value starting from 2nd index (chain: [2,3],[4,5]) we get 2. Thus there is a need to max over all the possible
max chain values.

    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, new Comparator<int[]>() {
   @Override
   public int compare(int[] o1, int[] o2) {
    int cmp = o1[0] - o2[0];
    return cmp != 0 ? cmp : o1[1] - o2[1];
   }
  });
        
        int[] memo = new int[pairs.length];
  int result = 1;
        for(int i = 0; i < pairs.length; i++) {
         result = Math.max(chain(pairs, i, memo), result);
        }
        
        return result;
    }
    
    private int chain(int[][] pairs, int index, int[] memo) {        
        if(memo[index] != 0) {
            return memo[index];
        }
        
        int max = 0;
        for(int i = index + 1; i < pairs.length; i++) {
            if(pairs[index][1] < pairs[i][0]) {
                max = Math.max(chain(pairs, i, memo), max);    
            }
        }
        memo[index] = max + 1;
     
        return memo[index];
    }

X. DP

If a chain of length k ends at some pairs[i], and pairs[i][1] < pairs[j][0], we can extend this chain to a chain of length k+1.

Sort the pairs by first coordinate, and let dp[i] be the length of the longest chain ending at pairs[i]. When i < j and pairs[i][1] < pairs[j][0], we can extend the chain, and so we have the candidate answer dp[j] = max(dp[j], dp[i] + 1).

• Time Complexity: $O(N^2)$ where $N$ is the length of pairs. There are two for loops, and $N^2$ dominates the sorting step.
• Space Complexity: $O(N)$ for sorting and to store dp

http://blog.csdn.net/u014688145/article/details/75911369
排序为了分阶段选择，动规为了记录所有子序列的值，毕竟它在选择上只需要当某个阶段的最大即可
public int findLongestChain(int[][] pairs) { int n = pairs.length; Arrays.sort(pairs, (a, b) -> (a[0] != b[0] ? a[0] - b[0] : a[1] - b[1])); int[] dp = new int[n]; dp[0] = 1; for (int i = 1; i < n; ++i){ for (int j = 0; j < i; ++j){ if (pairs[i][0] > pairs[j][1]){ dp[i] = Math.max(dp[i], dp[j] + 1); } else{ dp[i] = Math.max(dp[i], dp[j]); } } } return dp[n - 1]; }
https://discuss.leetcode.com/topic/96824/java-solution-10-lines-dp

    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
        
        int i, j, max = 0, n = pairs.length;
        int dp[] = new int[n];
      
        for (i = 0; i < n; i++) dp[i] = 1;
        
        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++)
                if (pairs[i][0] > pairs[j][1] && dp[i] < dp[j] + 1)
                    dp[i] = dp[j] + 1;

        for (i = 0; i < n; i++) if (max < dp[i]) max = dp[i];
        
        return max;
    }

http://www.geeksforgeeks.org/dynamic-programming-set-20-maximum-length-chain-of-pairs/

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.

static int maxChainLength(Pair arr[], int n)
{
   int i, j, max = 0;
   int mcl[] = new int[n];
   /* Initialize MCL (max chain length) values for all indexes */
   for ( i = 0; i < n; i++ )
      mcl[i] = 1;
   /* Compute optimized chain length values in bottom up manner */
   for ( i = 1; i < n; i++ )
      for ( j = 0; j < i; j++ )
         if ( arr[i].a > arr[j].b && mcl[i] < mcl[j] + 1)
            mcl[i] = mcl[j] + 1;
   // mcl[i] now stores the maximum chain length ending with pair i
   /* Pick maximum of all MCL values */
   for ( i = 0; i < n; i++ )
      if ( max < mcl[i] )
         max = mcl[i];
   return max;
}

X. Videos
Maximum Length Chain of Pairs | Dynamic Programming (Set 20) | GeeksforGeeks