# [leetcode solution/57]Insert Interval

Datetime:2017-04-01 05:40:01         Topic: LeetCode          Share        Original >>

Given a set of non-overlapping intervals, insert a new interval into the intervals (meger if necesary).

You may assume the intervals were initially sorted according to theis start points.

Example 1:

Given intervals [[1,3],[6,9]], insert and merge [2,5] 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]

## solution

• If we know the the interval after inserting/merging new interval into intervals, the problem is solved.
• Let’s decide the start point and end point of the new interval after inserting/merging.
• How to find the new start point:
• if start point is contained in an interval T of intervals. then new start point is the start point of T.
• if start point is not contained by any itnerval of intervals, then new start point is the same as it was.
• How to find the new end point.
• if end point is contained in an interval T of intervals. then new ned point is the end point of T.
• otherwise, the new end point is the same as it was.
• output the result
• for each interval in intervals, if it is contained in the new interval, ignore it because it was used to merge into the new interval.
• if we find interval with start point is more than the endpoint of new interval, it’s time to insert the new interval into our result.

## code

```/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
vector<Interval> ret;
if (intervals.empty()) {
ret.push_back(newInterval);
} else {
Interval final;
int n = intervals.size();
int start = newInterval.start;
int end = newInterval.end;
if (start < intervals[0].start) {
final.start = start;
}
if (start > intervals[n - 1].end) {
final.start = start;
}
final.end = end;
for (int i = 0; i < n; ++i) {
// decide start
if (start >= intervals[i].start && start <= intervals[i].end) {
final.start = intervals[i].start;
}
if (i >= 1 && start > intervals[i - 1].end && start < intervals[i].start) {
final.start = start;
if (start == intervals[i - 1].end) {
final.start = intervals[i - 1].start;
}
}
//decide end
if (end >= intervals[i].start && end <= intervals[i].end) {
final.end = intervals[i].end;
}
}
std::cout << "final: [" << final.start << ", " << final.end << "]" << std::endl;
// output result
for (int i = 0; i < n; ++i) {
if (final.start <= intervals[i].start && final.end >= intervals[i].end) {
continue;
}
if (!add && intervals[i].start > final.end) {
ret.push_back(final);
}
ret.push_back(intervals[i]);
}
ret.push_back(final);
}
}
return ret;
}
};
```