## Saturday, December 22, 2012

### [LeetCode] 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]`.
» Solve this problem

[解题思路]

[Code]
``````1:   vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      vector<Interval> result;
5:      result.push_back(newInterval);
6:      for(int i=0; i< intervals.size(); i++)
7:      {
8:        Interval newInt = result.back();
9:        result.pop_back();
10:        Interval* cur = &intervals[i];
11:        if(cur->end < newInt.start)
12:        {
13:          result.push_back(*cur);
14:          result.push_back(newInt);
15:        }
16:        else if(cur->start > newInt.end)
17:        {
18:          result.push_back(newInt);
19:          result.push_back(*cur);
20:        }
21:        else
22:        {
23:          newInt.start = min(cur->start, newInt.start);
24:          newInt.end = max(cur->end, newInt.end);
25:          result.push_back(newInt);
26:        }
27:      }
28:      return result;
29:    }
``````

[发散]

Update: 03/14/3013. Refactor code

``````1:       vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
2:            vector<Interval>::iterator it = intervals.begin();
3:            while(it!= intervals.end())
4:            {
5:                 if(newInterval.end<it->start)
6:                 {
7:                      intervals.insert(it, newInterval);
8:                      return intervals;
9:                 }
10:                 else if(newInterval.start > it->end)
11:                 {
12:                      it++;
13:                      continue;
14:                 }
15:                 else
16:                 {
17:                      newInterval.start = min(newInterval.start, it->start);
18:                      newInterval.end = max(newInterval.end, it->end);
19:                      ````it =intervals.erase(it);````
20:                 }
21:            }
22:            intervals.insert(intervals.end(), newInterval);
23:            return intervals;
24:       }
``````