Java solution with O(nlogn) time O(1) space


  • 0
    M
    class Solution {
    	public int findLongestChain(int[][] pairs) {
    		Arrays.sort(pairs, (p1, p2) -> {
    			if (p1[0] != p2[0]) {
    				return p1[0]-p2[0];
    			} else {
    				return p1[1]-p2[1];
    			}
    		});
            int count = 1;
            int end = pairs[0][1];
    		for (int[] pair : pairs) {
                if (end < pair[0]) {
                    count++;
                    end = pair[1];
                } else if (pair[1] < end) {
                    end = pair[1];
                }
            }
    
    		return count;
    	}
    }
    

Log in to reply
 

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