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在之后,则继续扫描
2.如果newInterval在之前,则直接插入然后返回。
3.如果newInterval在之间(只要出去上面两种情况是在之间),则merge,merge的过程是求两个interval的并集。然后删掉原来的数组元素,用新的这个并集代替newInterval,继续搜索,直到不需要merge(数组结束或者条件2), 然后将新的interval插入i即可,要注意remove数组元素的时候,i也要相应的–。不然会跳过一个值。

/**
 * 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 ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        if (newInterval == null)
            return intervals;
        if (intervals.size() == 0)
        {
            intervals.add(newInterval);
            return intervals;
        }
        Interval temp = newInterval;
        for (int i = 0; i < intervals.size(); i++)
        {
            Interval curr = intervals.get(i);
            if (curr.start > temp.end) //after the interval, return
            {
                intervals.add(i, temp);
                return intervals;
            }
            else if (curr.end < temp.start) // before interval continue
                continue;
            else {// overlap, merge
                int start = Math.min(temp.start, curr.start);
                int end = Math.max(temp.end, curr.end);
                temp = new Interval(start, end);
                intervals.remove(i);
                i--;// size shrink, i move forward;
            }
        }
        intervals.add(temp);
        return intervals;
    }
}

The above method takes O(n) time, there is a way using binary search which will have time complexity of Ologn.

First find the first (largest) index with a start that is smaller than the newInterval start, then find the first(largest) index with a start that is smaller than newInterval end. Then merge the result accordingly.

/**
 * 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 ArrayList insert(ArrayList intervals, Interval newInterval) {
        // find first element less than new interval start
        int first = binarySearch(intervals, newInterval.start);
        int last = binarySearch(intervals, newInterval.end);
        if (first == -1) {
            if (last == -1) {
                intervals.add(0, newInterval);
            }
            else {
                int e = Math.max(intervals.get(last).end, newInterval.end);
                Interval n = new Interval(newInterval.start, e);
                for (int i = 0; i = newInterval.start) {
                int e = Math.max(intervals.get(last).end, newInterval.end);
                Interval n = new Interval(intervals.get(first).start, e);
                for (int i = first; i &lt;= last; i++) {
                    intervals.remove(first);
                }
                intervals.add(first, n);
            }
            else {
                int e = Math.max(intervals.get(last).end, newInterval.end);
                Interval n = new Interval(newInterval.start, e);
                for (int i = first + 1; i &lt;= last; i++) {
                    intervals.remove(first + 1);
                }
                intervals.add(first + 1, n);
            }
        }
        return intervals;
    }
    
    //binary search to find either the target or the first interval with start less than target
    public int binarySearch(ArrayList intervals, int target) { 
        if (intervals.size() == 0)
            return -1;
        int start = 0;
        int end = intervals.size()-1;
        while(start &lt;= end) {
            int mid = (start + end)/2;
            if (intervals.get(mid).start == target)
                return mid;
            if (intervals.get(mid).start &lt; target) {
                start = mid + 1;
            }
            else
                end = mid - 1;
        }
        return end;
    }
}

Idea is simple, first find the first element that could overlap with the new interval. then merge the interval in, then keep searching until all the overlapping intervals are merged

/**
 * 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 ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        int index = -1;// the first interval that (might) overlap with the new interval
        for (int i = 0; i < intervals.size(); i++) {
            if (intervals.get(i).end >= newInterval.start) {
                index = i;
                break;
            }
        }
        //new interval should be appended to the end
        if (index == -1) {
            intervals.add(newInterval);
            return intervals;
        }
            
        Interval in = intervals.get(index);
        // no overlap, insert directly
        if (in.start > newInterval.end) {
            intervals.add(index, newInterval);
            return intervals;
        }
        //overlap, merge
        else {
            in.start = Math.min(newInterval.start, in.start);
            in.end = Math.max(newInterval.end, in.end);
        }
        //then try to merge all the rest of the
        while(index != intervals.size() - 1) { 
            if (in.end >= intervals.get(index + 1).start) {
                in.end = Math.max(in.end, intervals.get(index+1).end);
                intervals.remove(index + 1);
            }
            else
                break;
        }
        return intervals;
    }
}

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