57.Insert Interval¶
Tags: Hard
Array
Sort
Links: https://leetcode.com/problems/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:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
这道题目很容易就联想到56题,把newInterval
插入到intervals
里排个序,剩下就方法同理了。
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
intervals.push_back(newInterval);
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
res.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); ++i) {
if (intervals[i][0] > res.back()[1]) {
res.push_back(intervals[i]);
}
else {
res.back()[1] = max(intervals[i][1], res.back()[1]);
}
}
return res;
}
};
Runtime: 28 ms, faster than 15.95% of C++ online submissions for Insert Interval.
Memory Usage: 12.6 MB, less than 40.00% of C++ online submissions for Insert Interval.
从运行的结果来看,算法不太理想,因为注意到这个题和原来的问题有一个比较明显的区别,就是数组本来就是排好序的,所以应该充分利用这一点。
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> res;
int cur = 0, n = intervals.size();
while (cur < n && newInterval[0] > intervals[cur][1])
res.push_back(intervals[cur++]);
while (cur < n && intervals[cur][0] <= newInterval[1]) {
newInterval[0] = min(newInterval[0], intervals[cur][0]);
newInterval[1] = max(newInterval[1], intervals[cur][1]);
++cur;
}
res.push_back(newInterval);
while (cur < n) res.push_back(intervals[cur++]);
return res;
}
};
处理起来主要分为三段进行处理,因为区间序列有序且不重叠,所以需要去界定newInterval
的左端点在什么位置,很显然,如果当前区间的右端点小于新区间的左端点,那么必然没有重叠的部分。所以直接放入结果数组即可。
如果新区间和当前区间产生了重叠,但是并不清楚它覆盖了多大的范围,采取的策略就是逐个探测并合并。什么情况停止合并,显然是没有和newInterval
重叠的时候,那么就是新区间的右端点小于intervals
的左端点,所以余下的部分直接推入结果数组即可。
进一步思考:因为题目里限定了区间是没有重叠的,如果把这个条件去掉,但是区间仍然是有序的,那么就需要先进行一次区间合并,然后再按照上面的算法遍历一便,时间复杂度不会改变,仍然是O(n)。