Java sort solution - Longest Increasing Subsequence


  • 0

    EDIT : Other solutions are better than this since they sort by pair ends, instead of pair starts. :)

    The idea is to sort the pairs on their start.
    The rest of the idea is to do the longest increasing subsequence with binary search.
    Basically first ignore the ones with duplicate start(since you've already picked the best choice). For other pairs, don't take action if something needs to be replaced in the chain with same 'end'. Also, consider them equal (a[1] == b[0]) and take no action on them.

    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a,b)->a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
    
        List<int[]> chain = new ArrayList<>();
        chain.add(pairs[0]);
        for(int i = 1; i < pairs.length; i++) {
            int[] pair = pairs[i];
            if(pairs[i][0] == pairs[i-1][0]) continue;
            int idx = Collections.binarySearch(chain, pair,(a,b) -> a[1] == b[0] ? 0 : a[1] - b[1]);
            if(idx < 0) {
                if(-idx-1 < chain.size()) chain.set(-idx-1, pair);
                else {
                    if(chain.get(chain.size()-1)[1] > pair[1]) {
                        chain.set(-idx-1-1, pair);
                    }else if(chain.get(chain.size()-1)[1] < pair[0]){
                        chain.add(pair);
                    }
                }
            }
        }
        return chain.size();
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.