# 57. Insert Interval

Description:

https://leetcode.com/problems/insert-interval/#/description

Algorithm:

Firstly, I used similar algorithm as I used in 56. Merge Intervals. The code is shown in Code1. The timing is 19ms (beats 26%). So other methods should be tried.

Use the property of ordered and non-overlap. Check one by one:

Use int start and pair to record the new merged interval, initialize start = newInterval.start, end = newInterval.end

• if intervals[i].end<start
• push back intervals[i]
• if intervals[i].start>end
• push back newInterval
• push back intervals[i]
• else
• push back min(start), max(end)

Code1:

```class Solution1 { public: vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) { vector<Interval> result; if (intervals.size() == 0) { result.push_back(newInterval); return result; } Interval tmp; map <int, int> mapping; for (int i = 0; i < intervals.size();i++) { mapping[intervals[i].start] = INT_MIN; } mapping[newInterval.start] = INT_MIN; for (int i = 0; i < intervals.size();i++) { mapping[intervals[i].start] = max(intervals[i].end, mapping[intervals[i].start]); } mapping[newInterval.start] = max(mapping[newInterval.start], newInterval.end);```

``` ```

```map<int, int>::iterator it = mapping.begin(); int begin = it->first, end = it->second; for (it = mapping.begin(); it != mapping.end();it++) { if (it->first <= end) { end = max(it->second, end); } else { tmp = Interval(begin, end); result.push_back(tmp); begin = it->first; end = it->second; } } tmp = Interval(begin, end); result.push_back(tmp); return result; } };```

Code2:

```class Solution2 { public: vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) { int start = newInterval.start, end = newInterval.end; vector<Interval> res; int inserted = false; for (int i = 0;i<intervals.size();i++) { if (inserted == false) { if (intervals[i].start>end) { res.push_back(Interval(start, end)); res.push_back(intervals[i]); inserted = true; } else if (intervals[i].end<start) { res.push_back(intervals[i]); } else { start = min(start, intervals[i].start); end = max(end, intervals[i].end); } } else { res.push_back(intervals[i]); } } if (inserted == false) res.push_back(Interval(start, end)); return res;```

``` ```

```} };```

Timing:

O(n)

Timing of the maps: http://blog.csdn.net/wusecaiyun/article/details/46723363