Insert Interval

Leave a comment

December 18, 2016 by oneOokay

Insert Interval

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].


Overlapping, Intervals Related

直接一个一个比.

  • 不要想用merge interval的方法,因为时间复杂度是O(NlogN).
  • 也不要想用binary search, 也可以做但是比较messy.

 

找到最后一个Interval使得它的end < newInterval.start.(不能==, 如果==的话就要把newInterval和它进行merge了)

开始merge: 继续while loop往后找:如果Interval的start<=newInterval.end,要进行merge:

  1. 把当前的interval移掉.注意这里index不需要++,因为原来的元素移除掉了,index不变,当前位置上的元素就是后面的那个.
  2. 维持一个Interval insert,不断更新它的start和end的值:
    1. start为自身值和当前interval.start的较小值
    2. end为自身值和当前interval.end的较大值.
  3. while loop结束:表示当前index位置的interval的start值是大于insert.end的.已经不需要继续再merge了.
  4. 把insert加入到list位于index的位置.返回intervals.
public List insert(List intervals, Interval newInterval) {
        int index = 0, size = intervals.size();
        //find the last interval whose end <= new.start
        while (index < size && intervals.get(index).end < newInterval.start) index ++;
        Interval insert = newInterval;
//这里一定要用intervals.size(),因为intervals的size是随着remove元素而变化的.
        while (index < intervals.size() && intervals.get(index).start <= newInterval.end){
            insert.start = Math.min(insert.start, intervals.get(index).start);
            insert.end = Math.max(insert.end, intervals.get(index).end);
            intervals.remove(index);
        }
        intervals.add(index, insert);
        return intervals;
    }

//另外一个for loop的解法.trick在于,在把newInterval merge完之后,把它设为null
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
 if(newInterval == null) return intervals;
 List<Interval> res = new ArrayList<>();
 if (intervals == null || intervals.size() == 0){
 res.add(newInterval);
 return res;
 }
 Interval cur;
 for (int i = 0; i < intervals.size(); i ++){
 cur = intervals.get(i);
 if(newInterval == null || cur.end < newInterval.start){
 res.add(cur);
 continue;
 }
 
 if(cur.start > newInterval.end){
 res.add(newInterval);
 res.add(cur);
 newInterval = null;
 continue;
 }
 
 newInterval.start = Math.min(newInterval.start, cur.start);
 newInterval.end = Math.max(newInterval.end, cur.end); 
 }
 //最后对newInterval是否为null判断
 if(newInterval != null)
 res.add(newInterval);
 return res;
 }
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

%d bloggers like this: