Leetcode–Insert Interval

The Problem:

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Notes:

  1. The original list is valid, so we can take advantage of that, when traversing the list, if the new interval overlap with any in the original list, remove the one in the list, and update the new interval to the merge of those two.
  2. Use iterator to operate (add/remove) on the list at the same time of traversing. Note that when doing add(), should go to previous first, because when get to know the location of add, in fact we need add in front of current.
  3. To make the code concise and easy to read : For the condition to find overlapping can be very messy to list 4 overlapping ways, instead find those no-overlapping case first, and all overlapping case will be in else, then the merge can be done using Math.min/max instead of consider each case individually.

Java Solution

/**
 * 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 List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if(intervals.size()==0 ){
            intervals.add(newInterval);
            return intervals;
        }
        
        ListIterator<Interval> iterator = intervals.listIterator();
        boolean added = false;
        while(iterator.hasNext()){
            Interval  iter= iterator.next();
            
            if(iter.end < newInterval.start){
                continue;
            }
            else if (iter.start > newInterval.end){
                iterator.previous();
                iterator.add(newInterval);
                return intervals;
            }
            else{
                newInterval.start = Math.min(newInterval.start, iter.start);
                newInterval.end = Math.max(newInterval.end, iter.end);
                iterator.remove();
            }

        }
        intervals.add(newInterval);
        return intervals;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s