Java greedy solution


  • 0
    S
     * Definition for an interval.
     * public class Interval {
     *     int start;
     *     int end;
     *     Interval() { start = 0; end = 0; }
     *     Interval(int s, int e) { start = s; end = e; }
     * }
     */
    public class Solution {
        public int eraseOverlapIntervals(Interval[] intervals) {
            int count = 0, i, n = intervals.length;
            if (n < 2)
                return 0;
            
            Arrays.sort(intervals, new Comparator<Interval>() {
                public int compare (Interval i1, Interval i2) {
                    if (i1.start != i2.start)
                        return i1.start - i2.start;
                    else
                        return i1.end - i2.end;
                }    
            });
            
            int end = intervals[0].end;
            
            for (i=1;i<n;i++) {
                if (intervals[i].start < end) {
                    count++;
                    end = Math.min(end, intervals[i].end);
                } else {
                    end = intervals[i].end;
                }
            }
            return count;
        }
    }

Log in to reply
 

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