Share my simple greedy solution, Java, 6ms


  • 1

    In order to get minimal interval(s) removed, we need try to delete interval(s) which is(are) as "large" as possible.

    How to say an interval is large -> wide span -> sort intervals first.

    public class Solution {
        public int eraseOverlapIntervals(Interval[] intervals) {
            if(intervals.length<2) return 0;
            Arrays.sort(intervals, new Comparator<Interval>(){
                public int compare(Interval A, Interval B){
                    if(A.start!=B.start) return A.start-B.start;
                    else return A.end-B.end;
                }
            });
            int ret=0;
            Interval pre = intervals[0];
            for(int i=1;i<intervals.length;i++){
                if(pre.end<=intervals[i].start) pre = intervals[i];
                else{
                    ret++;
                    if(pre.end>intervals[i].end) pre = intervals[i];
                }
            }
            return ret;
        }
    }
    

Log in to reply
 

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