AC Java In-place O(n) solution


  • 0
    K
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        	int j = intervals.size();
        	for(int i=0;i<intervals.size();i++) {
        		Interval in = intervals.get(i);
                    // when there is a overlap, create new interval.
        		if(in.start <= newInterval.start && newInterval.start <= in.end ||
        		   in.start <= newInterval.end && newInterval.end <= in.end ||
        		   in.start >= newInterval.start && in.end <= newInterval.end) {
                            // create a new interval
        			Interval n = new Interval(Math.min(in.start, newInterval.start), Math.max(in.end, newInterval.end));
                            // remove the overlapped interval
        			intervals.remove(i);
                            // make this as the new interval
        			newInterval = n;
                            // maintain the index where the new interval needs to go
        			j = Math.min(j, i);
                            // since an interval is removed, decrement i so that the subsequent interval is not missed
        			i--;
        		}
                    // we are past the stage of overlaps, if any. track the index and exit
        		if(newInterval.end < in.start) {
        		    j = Math.min(j, i);
        		    break;
        		}
        	}
        	intervals.add(j, newInterval);
            return intervals;
        }
    

Log in to reply
 

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