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];
                    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.