java o(nlogn), just using the normal function 80%


  • 0
    T
      public int findLongestChain(int[][] pairs) {
            Arrays.sort(pairs, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    if (o1[0] == o2[0]) {
                        return o1[1] - o2[1];
                    }
                    return o1[0] - o2[0];
                }
            });
            List<int[]> array = new ArrayList<>();
            int[] tmp = null;
            for (int[] pair : pairs) {
                if (tmp == null) {
                    array.add(pair);
                    tmp = pair;
                }else if (pair[0] != tmp[0]) {
                    array.add(pair);
                    tmp = pair;
                }
            }
            int res = 1;
            int[] pre = array.get(0);
            for (int i = 1; i < array.size(); i ++) {
                int[] cur = array.get(i);
                if (pre[1] < cur[0]) {
                    res ++;
                    pre = cur;
                }else if (pre[1] > cur[1]) {
                    pre = cur;
                }
            }
            return res;
        }
    

Log in to reply
 

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