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

C++:
01 vector<Interval> insert(vector<Interval> &intervals, Interval newInterval)
02  {
03        int start=newInterval.start;
04        int end=newInterval.end;
05        vector<Interval> result;
06        bool flag=false;
07        for(int i=0;i<intervals.size();i++){
08            if((flag==false)&&(intervals[i].end>=start)){
09                flag=true;
10                newInterval.start=
11                  start<intervals[i].start?start:intervals[i].start;
12                while((i<intervals.size())&&
                         (intervals[i].start<=end)){
13                    if(intervals[i].end>end)
14                        newInterval.end=intervals[i].end;
15                    i++;
16                }
17                result.push_back(newInterval);
18            }
19            if(i<intervals.size())
20                result.push_back(intervals[i]);
21        }
22        if(flag==false)
23             result.push_back(newInterval);
24        return result;
25 }
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

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