Java Solution, same as minimum number of arrows to burst bollons


  • 0
    F
    /**
     * 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; }
     * }
     */
    class Solution {
        public int eraseOverlapIntervals(Interval[] intervals) {
            if(intervals==null || intervals.length==0) {
                return 0;
            } else {
                int curEnd, cnt = 1;
                
                Arrays.sort(intervals, new Comparator<Interval>(){
                    @Override
                    public int compare(Interval i1, Interval i2) {
                        if(i1.start < i2.start) {
                            return -1;
                        } else if(i1.start > i2.start) {
                            return 1;
                        } else {
                            return 0;
                        }
                    }
                });
                curEnd = intervals[ 0 ].end;
                for(int idx = 1; idx < intervals.length; idx++) {
                    if(intervals[ idx ].start >= curEnd) {
                        cnt++;
                        curEnd = intervals[ idx ].end;
                    } else {
                        curEnd = Math.min(curEnd, intervals[ idx ].end);
                    }
                }
                
                return intervals.length-cnt;
            }
        }
    }
    

Log in to reply
 

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