Java Simple Greedy Answer


  • 0
    L

    Java Simple Greedy Answer

    public int eraseOverlapIntervals(Interval[] intervals) {
            Comparator<Interval> c = 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 i1.end - i2.end;
    				}
    			}
    		};
    		Arrays.sort(intervals, c);
    		Stack<Interval> stack = new Stack<Interval>();
    		int count = 0;
    		for (int i = 0; i < intervals.length; i++) {
    			if (stack.isEmpty()) {
    				stack.push(intervals[i]);
    			} else {
    				if (stack.peek().end > intervals[i].start) {
    					count++;
    					if (stack.peek().end > intervals[i].end) {
    					    stack.pop();
    						stack.push(intervals[i]);
    					}
    				} else {
    					stack.push(intervals[i]);
    				}
    			}
    		}
    		return count;
        }

Log in to reply
 

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