Recently I’m preparing for my very first technical interview so I think it might be a good idea to blog about my thoughts on some of the algorithmic questions here.

Most of the questions are from LeetCode OJ, you can find more questions here.

### [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]`

.

### [Analysis]

Let’s call the interval to be inserted *newInterval *while original intervals are given in a vector<Interval> called *intervals*.

The definition of *Interval* is given below:

/** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */

The basic idea is to scan through the intervals and compare *newInterval* with the interval being scanned. When we want to insert an interval among others, there are in total three cases:

- current interval doesn’t overlap with
*newInterval*and precedes*newInterval* - current interval doesn’t overlap with
*newInterval*and follows*newInterval* - the two overlap, in this case, we need to merge the two of them

Now, the key is to understand that *newInterval* always holds the interval **to be added**, but we are still not sure if we need a merge or to wait before doing so.

Also, I find it really helpful to deal with simple cases first, and only concentrate on the “need to merge” one at the end.

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { vector<Interval> res; for (int i=0; i<intervals.size(); ++i) { if (intervals[i].end < newInterval.start) { res.push_back(intervals[i]); } else if (intervals[i].start > newInterval.end) { res.push_back(newInterval); newInterval = intervals[i]; } else { // need a merge newInterval.start = min(intervals[i].start, newInterval.start); newInterval.end = max(intervals[i].end, newInterval.end); } } res.push_back(newInterval); return res; }

Note that one line 17, we always push_back *newInterval*, because that’s what is “to be” inserted, so if the *newInterval* turns out to be the last one, we need to push that as well.