Java O(nlogn) very simple!


  • 0
    Z
    public int findLongestChain(int[][] pairs) {
    		if (pairs == null || pairs.length == 0) return 0;
    		Arrays.sort(pairs, new Comparator<int []>() {
    			@Override
    			public int compare(int[] fir, int[] sec) {
    				if (fir[0] != sec[0]) return fir[0] - sec[0];
    				return fir[1] - sec[1];
    			}
    		});
    		int res = 1;
    		int lastEnd = pairs[0][1];
    		for (int i = 1; i < pairs.length; i++) {
    			if (lastEnd < pairs[i][0]) {
    				res++;
    				lastEnd = pairs[i][1];
    			} else {
    				lastEnd = Math.min(pairs[i][1], lastEnd);
    			}
    		}
            return res;
        }
    
    

Log in to reply
 

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