Java Two Greedy solutions, SAME as 435 Non-overlapping intervals


  • 0

    The greedy approach:
    whenever we found two intervals are overlapped we have to remove one. we keep the one with smaller end point so it has better chance to form chain with the next interval. We can either sort the intervals by start point or end point.

    1. sort by start point
        public static int findLongestChain(int[][] pairs) {
            if (pairs.length == 0) return 0;
            Arrays.sort(pairs, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] - o2[0];
                }
            });
            int remove = 0, end = pairs[0][1];
            for (int i = 1; i < pairs.length; i++) {
                if (pairs[i][0] <= end) {
                    remove++;
                    end = Math.min(end, pairs[i][1]);
                } else {
                    end = pairs[i][1];
                }
            }
            return pairs.length-remove;
        }
    
    1. sort by end point
        public static int findLongestChain(int[][] pairs) {
            if (pairs.length == 0) return 0;
            Arrays.sort(pairs, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[1] - o2[1];
                }
            });
            int end = pairs[0][1], remove = 0;
            for (int i = 1; i < pairs.length; i++) {
                if (pairs[i][0] <= end) remove++;
                else end = pairs[i][1];
            }
            return pairs.length - remove;
        }
    

Log in to reply
 

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