Java solution with explanation


  • 0

    At the beginning, I was sorting the intervals with starting time, but it failed with some cases. So I started to look up what I missed. This post Java: Least is Most by crickey180 points out that this is a classic greedy problem Interval Scheduling, check out the wiki to see more details:

    My idea is pretty similar as most of others, but instead of counting maximum number of non-overlapping intervals, I directly count the number of intervals we need to remove.

        public int eraseOverlapIntervals(Interval[] intervals) {
            if (intervals == null || intervals.length == 0)     return 0;
            Arrays.sort(intervals, new Comparator<Interval>() {
                public int compare(Interval a, Interval b) {
                    return a.end - b.end;
                } 
            });
            
            int count = 0;
            Interval pre = intervals[0];
            for (int i = 1; i < intervals.length; ++i) {
                //when we encounter an interval overlap with previous one, we remove it
                if (intervals[i].start < pre.end) {
                    count++;
                } else {
                    pre = intervals[i];
                }
            }
            return count;
        }
    

Log in to reply
 

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