LeetCode Insert Interval

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].


一个已经排好序的区间数组,现在要插入一个新的区间,并且如果能合并则需要合并。最简单的方法就是把新加入的区间和原有区间一起排个序,然后统一合并,问题就转换为LeetCode Merge Intervals了。

但是原有区间数组是已经按start排序了,所以有更简单的办法。我们可以分三个过程插入新的区间,首先把明显小于新区间的区间放到结果数组中,然后处理所有可能和新区间有overlap的区间,不断合并并更新新区间,直到无法再合并时,把新区间加入结果数组中,最后把明显大于新区间的区间放到结果数组中。

完整代码如下:

class Solution {
public:
	vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
		vector<Interval> ans;
		int i = 0, n = intervals.size();
		while (i < n&&intervals[i].end < newInterval.start)ans.push_back(intervals[i++]);
		while (i < n&&newInterval.end >= intervals[i].start) {
			newInterval.start = min(newInterval.start, intervals[i].start);
			newInterval.end = max(newInterval.end, intervals[i].end);
			++i;
		}
		ans.push_back(newInterval);
		while (i < n)ans.push_back(intervals[i++]);
		return ans;
	}
};

本代码提交AC,用时13MS。

Leave a Reply

Your email address will not be published. Required fields are marked *