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 /**
02  * Definition for an interval.
03  * struct Interval {
04  *     int start;
05  *     int end;
06  *     Interval() : start(0), end(0) {}
07  *     Interval(int s, int e) : start(s), end(e) {}
08  * };
09  */
10 class Solution {
11 public:
12     vector<Interval> insert(vector<Interval> &intervals,
13                             Interval newInterval) {
14         // Start typing your C/C++ solution below
15         // DO NOT write int main() function
16         int start=newInterval.start;
17         int end=newInterval.end;
18         int i=0;
19         vector<Interval> result;
20         for(;i<intervals.size();i++)
21         {
22             if(intervals[i].end<start)
23             {
24                 result.push_back(intervals[i]);
25             }
26             else
27             {
28                 break;
29             }
30         }
31         if(i==intervals.size())
32         {
33             result.push_back(newInterval);
34             return result;
35         }
36         int mergeStart=intervals[i].start<start?
37           intervals[i].start:start;
38         int mergeEnd=end;
39         for(;i<intervals.size();i++)
40         {
41             if(intervals[i].start<=end)
42             {
43                 mergeEnd=intervals[i].end>end?
44                   intervals[i].end:end;
45             }
46             else
47             {
48                 break;
49             }
50         }
51         Interval mergeInterval;
52         mergeInterval.start=mergeStart;
53         mergeInterval.end=mergeEnd;
54         result.push_back(mergeInterval);
55         for(;i<intervals.size();i++)
56         {
57             result.push_back(intervals[i]);
58         }
59         return result;
60     }
61 };
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