JAVA Solution beats 99.26% - solve by finding max non-overlapping intervals


  • 1
    C

    The basic idea is finding the maximum non-overlapping intervals, and the erased intervals count is the whole length minus the non-overlapping intervals count.
    For example:
    [1,2],[2,3],[1,3],[3,4]
    after sorting:
    [1,2],[1,3],[2,3],[3,4]
    the max non-overlapping intervals are:
    [1,2],[2,3],[3,4] => count = 3;
    the intervals that should be removed is [1,3], and the count = len - max_non_overlapping = 4 - 3 = 1

    public int eraseOverlapIntervals(Interval[] intervals) {
            Arrays.sort(intervals, new Comparator<Interval>() {
                public int compare(Interval a, Interval b) {
                    if (a.start == b.start) return a.end - b.end;
                    return a.start - b.start;
                }
            });
            
            int len = intervals.length;
            if (len == 0) {
                return 0;
            }
            int maxNonOverLapping = 1, prevStart = intervals[0].start, prevEnd = intervals[0].end;
            for (int i = 1; i < len; i++) {
                if (prevEnd > intervals[i].start && intervals[i].end < prevEnd) {
                    // if the current interval has smaller end value, replace previous interval with current on to allow more future non-overlapping intervals
                    prevEnd = intervals[i].end;
                } else if (prevEnd <= intervals[i].start) {
                    // The current interval is non-overlapping interval to previous interval
                    maxNonOverLapping++;
                    prevStart = prevEnd;
                    prevEnd = intervals[i].end;
                }
            }
            return len-maxNonOverLapping;
        }
    

Log in to reply
 

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