Overlapping, Intervals Related

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


想法1: 直接把newInterval加入到intervals里面,再重新merge一遍. 时间复杂度O(NlogN)

二分法也可以做但是感觉有点messy. 以后试一下.

方法1:

  1. 找到最后一个Interval使得它的end < newInterval.start.(不能==, 如果==的话就要把newInterval和它进行merge了)
  2. 开始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;
        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;
    }
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: