MaximumLengthOfPairChain [source code]

public class MaximumLengthOfPairChain {
static
/******************************************************************************/
public class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a,b) -> a[1] - b[1]);
        int end = pairs[0][1], len = 1;
        for (int i = 1; i < pairs.length; i++) {
            if (pairs[i][0] > end) {
                end = pairs[i][1];
                len++;
            }
        }
        return len;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MaximumLengthOfPairChain.Solution tester = new MaximumLengthOfPairChain.Solution();
    }
}

题目给出一个新的definition, 自己理解的时候要注意细节:

• follow是一个暗示先后顺序的词. 按照题目实际给出的定义, 越大越later, 所以越大反而越是follower;
• b < c: 不能取等号;

最值搜索问题, 一般我们有两种思路:

• 确定搜索
• 模糊搜索

确定搜索, 一般指的是比如实际上可以通过类似人逻辑的分析, 想到怎样deterministic的找到这个最值. 这种你就正常算法来做就行了; 一般来说, greedy其实也可以算作是在确定搜索里面的, 因为greedy的next move策略实际上是固定的很清晰的;

模糊搜索, 其实就是这里tag上的DP; DP的原理其实就是一个优化了的DFS, 也就是一个优化了之后的穷搜, explore all possibilities. 其实我们也不知道怎么找到这个最值, 只能用一个exhaustive的做法, 来"盲目"搜索一下; 当然有时候其实DP都用不了, 那么基本就是一个普通的DFS, 顶多再加一个backtracking;

一般来说, 刚拿到一个题目的时候, 如果能够想到确定搜索的话(deterministic search), 当然是最好的, 这种做法一般都比模糊搜索要快; 不过如果实在是想不到确定搜索, 那么是可以适当考虑resort to DP之类的做法的;

之前关于DP的总结自己回想一下:

• DP的核心点在于研究memo表格:
  • 几个index, 以及每个index代表什么? 这里有一个肯定是input的长度, 另外一个呢?
  • entry是什么? 也就是opt value, which is also the DP value;
    • 思考entry这个dp return value的时候, 我们往往忘记一个问题, 就是虽然DP问题很多时候看起来是找一个value, 但是实际上你真正要找的是一个跟这个value对应的解. 所以你真正自己研究怎么设置这个value, 或者怎么更新这个value的时候, 脑子里思考的对象应该是这个optimal solution, 而不是单纯的optimal value.
    • 这个DP value虽然很多时候跟target value不是一个东西, 但是要记住, 我们最终是要求这个DP value是可以用来组合或者计算出来target value的; 所以很多时候, 适当的思考一下我们要的到底是什么, 可以帮助我们找到设置DP value的正确方式;
    • 另外很多时候要强调一个root participation. 这个也是之前tree问题的时候总结出来的;
    • 有些时候还要维护一些global的值.
• 之前学习DP的时候还知道, 要思考root decision, 其实这个是一个和root participation很类似的概念;

还是没有什么思路, 大概看了一眼discussion, 好像不少人直接用sort来做了; sort之后做, 往往其实也就是一个greedy的做法了; 有点失误, 这个解法按理说我应该想到的;

不对, 这个题目sort之后其实也不是那么trivial的, sort之后, 还是要用一个LIS的算法来做. LIS的算法本身是属于一个DP算法的;

这个题目还是受tag的影响太多了, 就想着用DP来做. 是不是以后可以有一个想法, 首先肯定是找确定算法, 不行就思考DP, 如果DP感觉怎么都想不到(往往是表格不知道怎么设定), 可以回过头来考虑是否可以用greedy来做?

按照答案写了一个greedy算法, 最后的速度是114(37). 重新提交了一下,波动在40%左右, 没有想象中的快;

这个是sort之后的解法:

This is equivalent to interval scheduling problem.

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;  
}

这个解法实际上没有用到LIS那么复杂的算法. sort之后, [0]的位置一定会被包括在最后的最长chain里面: 这个可以自己举几个例子看看就知道了: 假如最长chain的长度超过1, 也就是最少是2, 并且它的第一个不是[0], 假设它是[k], 那么我们总是可以把pair[k]换成pair[0]并且保持最终的length不变: pair[0][1] <= pair[k][1], 所以[k]能够胜任的位置, [0]也始终能够可以胜任;

知道了这一点, 我们就有一个确定点了;

• 这类题目一个麻烦的地方就是让你找一个longest什么东西, 但是你根本不知道这个东西在哪里, 很多时候你不仅不知道起点在哪里, 终点在哪里, 你甚至连比如这里的这个sequence是否consecutive都不知道; 针对这个uncertainty的问题, 很多时候最好的做法就是消除这个uncertainty.
  • 这里消除uncertainty的做法是找到hidden certainty, 不过很多时候并不是这么幸运的;
  • 更多时候的做法其实就是分情况讨论, 或者说枚举;

确定了起点之后, 后面的做法就不是很难理解了: 直接选定longest chain的第一个pair, 然后跳过所有被当前pair吞并的(与当前pair有overlapping的), 找到下一个; 中间注意一个边界处理就行了;

另外注意他这里sort的做法. 他是只sort end的, 对于end tie的情况, 他其实并不处理; 事实上在这个问题上, 是没有关系的, 比如(1,2), (1,4), (3,4), 后面的两个pair是tie, 我们其实就不用管:

• 如果是现在这个顺序, 我们(1,2)出发, (1,3)会被跳过, 然后(3,4)会被捕捉;
• 如果是调换顺序: (1,2)将无法跳过(1,4), 而是直接捕捉(3,4), 然后(3,4)会跳过(1,4), 所以最后的结果其实是一样的;

注意他这里循环的写法, i初始化的位置是-1, 然后是一个前置++开始操作;

这个是一个等价的写法, 不过循环写的相对好看一些:

    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;  
    }

底下有一个人尝试给出一个证明:

Prove by exchange:
Let C be the pair chain of the maximum length, C[p] be the p-th pair in C. Suppose there is a pair q such that q[0] > C[p-1][1] and q[1] <= C[p][1]. We replace C[p] with q, the resulting pair chain will not be shorter than the original C. Therefore, we can do such replacement as many as we want.
QED

不过我感觉这个证明其实有点没头没脑的; 而且这个算法真的需要证明吗? 我感觉唯一需要证明的就是pairs[0]一定在这个chain里面. 知道了起点之后, 按照not overlapping的原则选就行了; 注意, 不可能有some other longer chain that does not start from pairs[0], because this is why we proved pairs[0] to be in the longest chain in the first place;

这个是另外一个做法:

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

public class Solution {  
    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;  
    }  
}

虽然也是依赖sort降低难度, 但是在sort之后的处理上面, 相对于前面的greedy做法, 这里的做法则更加倾向于DP一点;

注意这里sort的是start, 而不是end. 下面有人对此评论:

Just some thoughts on this problem.

Sorting on either the first element or the second, this problem essentially reduces to the Longest Increasing Subsequence problem and we can use DP to solve it.

However, if we want to use Greedy to solve this problem, we need to sort on the second element. Sorting on the first element will not work. For example, try (8,9) (10,11) (1,100).

My initial trial uses DFS+memorization. It is not efficient in both time and space though.

这个人最后自己写的做法是DFS, 基本就是穷搜了. 如果不用sort, 这个问题的难度陡增;

复习了一下LIS算法, 对这个算法再看还是可以理解的, 这里的一个核心操作是:

                if (pairs[i][0] > pairs[j][1] && dp[i] < dp[j] + 1)  
                    dp[i] = dp[j] + 1;

这里header里面两个条件:

• pairs[i][0] > pairs[j][1]: pairs[i] can be appended to the LIS ending at pairs[j];
• dp[i] < dp[j] + 1: such an appending would improve the length of the LIS ending at pairs[i]. 注意这里没有取等号: tie不算improvement;

这个算法最后的复杂度很可惜是不如greedy的, 只能做到N^2;(这里的写法是iteration版本, 复杂度比较好分析; 如果是recursion版本, 记得考虑每一个node的fanning: 这个是DP复杂度分析当中容易被忽视的一个点);

相比于之前的greedy解法, 我感觉这个解法其实更值得学习, 这个就是一个很传统的思路就能做出来, 先sort降低难度, 然后题目转化为一个熟悉的基本问题; 而greedy的解法, 如果是第一次做, 很多隐藏的assumption不容易想到也不容易证明:

• you can always include pairs[0];
• tie breaking does not matter;

真正自己写这样一个sort的时候, 我还是倾向于自己定义一下tie breaking的情形, 不要自己给自己留uncertainty: 很多时候, even a wrong certainty is bettern than uncertainty. 因为你做着做着最起码知道哪里错了. 当然, 这些premature and unjustified certainty/assumption自己在做了之后脑子里要稍微track一下, 不然真正后面出了问题不一定想的起来可能在哪里;

比如这个问题, 假如你想到sort之后, 你不知道sort start还是end, 那么你假设就sort start, 结果后面突然发现greedy做不起来, 这个时候你可以回过头来到这个存档点来思考一下, 是不是这个certainty选的不太好;

讲到这个tie breaking的问题, 突然想到, Arrays.sort到底是否stable?

Quicksort is used for arrays of primitive types while mergesort for Object[] arrays.

The main reason why mergesort is used for Objects that mergesort is stable - it does not reorder elements that are equal: http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

For primitives the stability of the sort is meaningless, as you cannot distinguish two values that are equal. Hence, quicksort is used (except when sorting an array of Objects, for which mergesort is performed). Moreover, quicksort can be done in place, so there is no need to allocate another array.

所以是stable的;

但是有人提出:

That said, JDK 7 no longer uses mergesort -- it uses the mythical TimSort!

听说这个sort非常的复杂, 但是也非常的快, 有时间再看了;

另外一个greedy的做法, 其实类似的:

Consider pairs as jobs, with [start time, end time],
Then the problem is converted to ask the maximum jobs we can accomplish.

public class Solution {  
    public int findLongestChain(int[][] pairs) {  
        if(pairs == null || pairs.length ==0 ) return 0;  
        Arrays.sort(pairs, (a, b) -> (a[1] - b[1]));  
        int res=1, end = pairs[0][1];  
        for(int i =1; i<pairs.length; i++) {  
            if(pairs[i][0]>end){  
                res++;  
                end = pairs[i][1];  
            }  
        }  
        return res;  
    }  
}

与其在当前位置跳子, 直接一个流处理感觉更简练易懂;

而且实际上你可以说这个是一个更加具有DP性质的解法: 这里的这个end其实就是我们要的DP value. 随着length进行维护, 同时最终可以用来计算target value(注意, 这个end并不直接就是length of longest chain);

这个是另外一个依赖于LIS的做法, 不过顺序反过来, 有点像我自己写的那个recursion的版本, instead of finding LIS_ending_at each index, we find LIS_starting_at each index. 最后的结果应该都是一样的;

public class Solution {  
    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];  
    }  
}

Problem Description

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:

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

Difficulty:Medium
Total Accepted:4.6K
Total Submissions:9.9K
Contributor: ashishmadaan6
Companies
amazon
Related Topics
dynamic programming
Similar Questions
Longest Increasing Subsequence Increasing Subsequences

Problem Description

这个是我自己在discussion里面po的关于跳子算法的说明:

I think the key to understanding this greedy algorithm is to understand two assumptions:
After sorting:

• The longest chain must contain pairs[0].
  • Suppose it doesn't, that is, suppose the longest chain C starts at pairs[k] for some k > 0. And we obviously have pairs[k][1] ≥ pairs[0][1] due to sorting. We can always form a new chain C' by replacing pairs[k] with pairs[0], whose length would be no shorter than C, obviously. We just have to prove C' to be also a chain without overlapping. This is trivial: pairs[0] ends no later than pairs[k], and if you can lead a chain with pairs[k], you can also lead a chain with pairs[0] without introducing new overlapping;
• Tie situations does not matter: you do not have to specify how to sort the pairs when the ends are at a tie.
  • Consider such an example: (1,2), (1,4), (3,4), we start at (1,2), and (1,4) is skipped. And then we add (3,4). If we have instead: (1,2), (3,4), (1,4), then we start at (1,2), and then we add (3,4), and then we skip (1,4). In the two different situations, the pair (1,4) (that is, the pair that is tied but has a smaller start) is skipped anyway, albeit by different is. You can directly try to prove the statement: when there are intervals with tying ends, the optimal solution will never choose the one with smaller start over the other one which has a relatively larger start. This is intuitive: same end and smaller start means longer and more overlapping, why bother.

I think the algorithm's strategy then justifies itself in the light of these two assumptions and needs no further proof. Hope this helps.