Java Solution with clear explain


  • 10

    First we sort the array by below rules

    • 1) sort by end, smaller end in front
    • 2) if end is same, sort by start, bigger start in front

    Then, visited array by end. If we visited next closest end interval, access the bigger start priority.

    /**
         * 16 / 16 test cases passed
         * Status: Accepted
         * Runtime: 9 - 10 ms
         *
         * @param intervals
         * @return
         */
    public int eraseOverlapIntervals(Interval[] intervals) {
            Arrays.sort(intervals, new Comparator<Interval>() {
                @Override
                public int compare(Interval o1, Interval o2) {
                    if (o1.end != o2.end) return o1.end - o2.end;  //first sort by end
                    return o2.start - o1.start;  //second sort by start
                }
            });
    
            int end = Integer.MIN_VALUE;
            int count = 0;
            for (Interval interval : intervals) {
                if (interval.start >= end) end = interval.end;
                else count++;
            }
    
            return count;
        }
    

  • 0
    I

    Question, what benefit do you get by doing:

    1. if end is same, sort by start, bigger start in front

  • 1

    @wintersliu when end is same, the bigger start one has greater possibility of convergence. So we can put those front. Actually, we only sort by end is ok, like below

    Arrays.sort(intervals, new Comparator<Interval>() {
        @Override
        public int compare(Interval o1, Interval o2) {
            return o1.end - o2.end;  //only sort by end
        }
    });
    

  • 0
    I

    @zhangCabbage Right, thanks for the explanation.


Log in to reply
 

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