Insert Interval

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:

  1. current interval doesn’t overlap with newInterval and precedes newInterval
  2. current interval doesn’t overlap with newInterval and follows newInterval
  3. 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.

Advertisements

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