insert a interval into set of non-overlapping intervals (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].

Thoughts:
We insert the new interval into the set of intervals according to their start time. Then we look back (i.e., left) to see if we can merge. Then we look right (i.e., right) to see if we can merge. For Example 2, the algorithm works as:

  1. Insert [4,9] into original set of intervals according to the start time. So we’ve got: [1,2],[3,5],[4,9],[6,7],[8,10],[12,16] after insertion.
  2. From [4,9], look back to see if we can merge. [3,5] can be merged with [4,9] so [3,5] will be deleted and we have a updated entry: [3,9]. Afterwards, the list becomes: [1,2],[3,9],[6,7],[8,10],[12,16].
  3. Continue to look to left. [1,2] cannot be merged with [3,9] so this is done.
  4. Start to look to the right. [3,9] can be merged with [6,7]. In fact, [3,9] will ‘absorb’ [6,7], so [6,7] will just be deleted. We have: [1,2],[3,9],[8,10],[12,16].
  5. Continue to look to the right. [3,9] can be merged with [8,10] so [8,10] will be deleted and we have a updated entry [3,10]. The list becomes: [1,2],[3,10],[12,16].
  6. [3,10] cannot be further merged with [12,16] so the result is just: [1,2],[3,10],[12,16].

Code (Java):

public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, 
                Interval newInterval) {
        int startIndex = 0;
        for(int i = -1; i < intervals.size(); ++i) {
            Interval current = i == -1 ? null : intervals.get(i);
            Interval next = i + 1 == intervals.size() ? null : intervals.get(i+1);
            if( (current == null || current.start <= newInterval.start) &&
                (next == null || newInterval.start <= next.start) )
                startIndex = i + 1;
        }
        ArrayList<Interval> sol = new ArrayList<Interval>();
        sol.addAll(intervals);
        sol.add(startIndex, newInterval);
        
        int i = startIndex;
        // shrink to left
        for(; i - 1 >= 0;) {
            Interval current = sol.get(i);
            Interval previous = sol.get(i - 1);
            if(current.start <= previous.end) {
                current.start = current.start >= previous.start ? 
                                previous.start : current.start;
                current.end = current.end >= previous.end?
                                current.end : previous.end;
                sol.remove(i-1);
                --i;
            } else {
                break;
            }
        }
        
        for(int j = i; j + 1 < sol.size();) {
            Interval current = sol.get(j);
            Interval next = sol.get(j + 1);
            if(current.end >= next.start) {
                current.start = current.start >= next.start ?
                                next.start : current.start;
                current.end = current.end >= next.end ? 
                                current.end : next.end;
                sol.remove(j+1);
            } else {
                break;
            }
        }
        
        return sol;
    }
}

Code (C++)
Thanks for this post.

class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> result;
        bool isLarge = true;
        
        for(vector<Interval>::iterator it = intervals.begin();
            it != intervals.end(); ++it) {
            if(it -> end < newInterval.start) {
                result.push_back(*it);
                continue;
            }
            if(it -> start > newInterval.end) {
                if(isLarge) {
                    result.push_back(newInterval);
                    isLarge = false;
                }
                result.push_back(*it);
                continue;
            }
            
            newInterval.start = min(it -> start, newInterval.start);
            newInterval.end = max(it -> end, newInterval.end);
        }
        
        if(isLarge)
            result.push_back(newInterval);
        
        return result;
    }
};
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: