NC222. 插入区间
描述
给定一个无重叠的，按照区间起点升序排列的区间列表，在列表中插入一个新区间，如果有原区间有重合，则合并，请返回插入后的区间列表。
数据范围：区间列表长度满足 
， 区间的左右端点满足 
示例1
输入:
[[2,5],[6,11]],[5,6]
输出:
[[2,11]]
示例2
输入:
[],[2,5]
输出:
[[2,5]]
NC222. 插入区间
描述
示例1
输入:
[[2,5],[6,11]],[5,6]
输出:
[[2,11]]
示例2
输入:
[],[2,5]
输出:
[[2,5]]
C++ 解法, 执行用时: 6ms, 内存消耗: 952KB, 提交时间: 2022-02-09
/**
* struct Interval {
* int start;
* int end;
* Interval(int s, int e) : start(start), end(e) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param Intervals Interval类vector
* @param newInterval Interval类
* @return Interval类vector
*/
int Max(int a, int b)
{
if (a > b)return a;
return b;
}
vector<Interval> insertInterval(vector<Interval>& Intervals, Interval newInterval) {
Intervals.push_back(newInterval);
sort(Intervals.begin(), Intervals.end(), [](Interval& a, Interval& b) {return a.start < b.start; });
vector<Interval> vec{ Intervals[0] };
for (int i = 1; i < Intervals.size(); i++)
{
if (vec.back().end >= Intervals[i].start)
{
vec.back().end = Max(vec.back().end, Intervals[i].end);
}
else {
vec.push_back(Intervals[i]);
}
}
return vec;
}
};
C++ 解法, 执行用时: 7ms, 内存消耗: 816KB, 提交时间: 2022-01-27
/**
* struct Interval {
* int start;
* int end;
* Interval(int s, int e) : start(start), end(e) {}
* };
*/
class Solution {
public:
/*
前言
1. 对于区间 S_1 = [l_1, r_1] 和 S_2 = [l_2, r_2]，如果它们之间没有重叠（没有交集），
说明要么 S_1 在 S_2 的左侧，此时有 r_1 < l_2；要么 S_1 在 S_2 的右侧，此时有 l_1 > r_2
2. 如果 r_1 < l_2 和 l_1 > r_2 二者均不满足，说明 S_1 和 S_2 必定有交集，
它们的交集即为 [max(l_1, l_2), min(r_1, r_2)]，并集即为 [min(l_1, l_2), max(r_1, r_2)]
方法一：模拟 - 思路清晰
思路与算法
在给定的区间集合 X 互不重叠的前提下，当我们需要插入一个新的区间 S=[left,right] 时，我们只需要：
1. 找出所有与区间 S 重叠的区间集合 X′；
2. 将 X′ 中的所有区间连带上区间 S 合并成一个大区间；
3. 最终的答案即为不与 X′ 重叠的区间以及合并后的大区间。
这样做的正确性在于，给定的区间集合中任意两个区间都是没有交集的，
因此所有需要合并的区间，就是所有与区间 S 重叠的区间。
并且，在给定的区间集合已经按照左端点排序的前提下，
所有与区间 S 重叠的区间在数组 intervals 中下标范围是连续的，
因此我们可以对所有的区间进行一次遍历，就可以找到这个连续的下标范围。
当我们遍历到区间 [l_i, r_i] 时：
1. 如果 r_i < left，说明 [l_i, r_i] 与 S 不重叠并且在其左侧，
我们可以直接将 [l_i, r_i] 加入答案；
2. 如果 l_i > right，说明 [l_i, r_i] 与 S 不重叠并且在其右侧，
我们可以直接将 [l_i, r_i] 加入答案；
3. 如果上面两种情况均不满足，说明 [l_i, r_i] 与 S 重叠，我们无需将 [l_i, r_i] 加入答案。
此时，我们需要将 S 与 [l_i, r_i] 合并，即将 S 更新为其与 [l_i, r_i] 的并集。
那么我们应当在什么时候将区间 S 加入答案呢？
由于我们需要保证答案也是按照左端点排序的，因此当我们遇到第一个 满足 l_i > right 的区间时，
说明以后遍历到的区间不会与 S 重叠，并且它们左端点一定会大于 S 的左端点。
此时我们就可以将 S 加入答案。特别地，如果不存在这样的区间，我们需要在遍历结束后，将 S 加入答案。
复杂度分析
时间复杂度：O(n)，其中 n 是数组 intervals 的长度，即给定的区间个数。
空间复杂度：O(1)。除了存储返回答案的空间以外，我们只需要额外的常数空间即可。
参考：
https://leetcode-cn.com/problems/insert-interval/solution/cha-ru-qu-jian-by-leetcode-solution/
*/
vector<Interval> insertInterval(vector<Interval>& Intervals, Interval newInterval) {
int left = newInterval.start;
int right = newInterval.end;
bool placed = false;
vector<Interval> ans;
for (const auto& interval: Intervals) { //遍历当前区间
if (interval.start > right) { // 当前区间在插入区间的右侧且无交集，如[[2,5]],[0,1]
if (!placed) { // 首次添加插入区间时执行，之后不用执行！
ans.push_back({left, right});
placed = true;
}
ans.push_back(interval);
}
else if (interval.end < left) { // 当前区间在插入区间的左侧且无交集，如[[2,5]],[8,9]
ans.push_back(interval);
}
else { // 当前区间与插入区间有交集，计算它们的并集，如[[2,5],[6,9]],[3,8]
left = min(left, interval.start);
right = max(right, interval.end);
}
}
if (!placed) { // 插入区间在集合所有区间右侧，则将插入区间添加至末尾
ans.push_back({left, right});
}
return ans;
}
/*
相同思路，另一种写法
*/
vector<Interval> insertInterval1_2(vector<Interval>& Intervals, Interval newInterval) {
vector<Interval> result;
int current_index = 0;
for (const auto& interval : Intervals) {
if (interval.end < newInterval.start) { //当前区间在插入区间的左侧且无交集
++current_index; //记录新插入区间的插入位置
result.emplace_back(interval);
} else if (interval.start > newInterval.end) { //当前区间在插入区间的右侧且无交集
result.emplace_back(interval); //最后会统一添加插入区间
} else { //当前区间与插入区间有交集，计算它们的并集 - 更新插入区间的左右边界
newInterval.start = min(newInterval.start, interval.start);
newInterval.end = max(newInterval.end, interval.end);
}
}
result.insert(result.begin() + current_index, newInterval); //最后统一添加插入区间
return result;
}
};
C++ 解法, 执行用时: 7ms, 内存消耗: 920KB, 提交时间: 2022-01-21
/**
* struct Interval {
* int start;
* int end;
* Interval(int s, int e) : start(start), end(e) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param Intervals Interval类vector
* @param newInterval Interval类
* @return Interval类vector
*/
vector<Interval> insertInterval(vector<Interval>& Intervals, Interval newInterval) {
vector<Interval> result;
int current_index = 0;
for (const auto& interval : Intervals) {
if (interval.end < newInterval.start) {
++current_index;
result.emplace_back(interval);
} else if (interval.start > newInterval.end) {
result.emplace_back(interval);
} else {
newInterval.start = min(newInterval.start, interval.start);
newInterval.end = max(newInterval.end, interval.end);
}
}
result.insert(result.begin() + current_index, newInterval);
return result;
}
};
C++ 解法, 执行用时: 7ms, 内存消耗: 972KB, 提交时间: 2021-11-21
/**
* struct Interval {
* int start;
* int end;
* Interval(int s, int e) : start(start), end(e) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param Intervals Interval类vector
* @param newInterval Interval类
* @return Interval类vector
*/
static bool compmin(Interval a,Interval b)
{
return a.start<b.start;
}
vector<Interval> insertInterval(vector<Interval>& Intervals, Interval newInterval) {
// write code here
Intervals.push_back(newInterval);
sort(Intervals.begin(), Intervals.end(),compmin);
vector<Interval> tempInterval;
tempInterval.push_back(Intervals[0]);
for (int i = 1; i < Intervals.size(); ++i) {
if (tempInterval[tempInterval.size() - 1].end >= Intervals[i].start) {
tempInterval[tempInterval.size() - 1].start = min(Intervals[i].start, tempInterval[tempInterval.size() - 1].start);
tempInterval[tempInterval.size() - 1].end = max(Intervals[i].end, tempInterval[tempInterval.size() - 1].end);
}
else {
tempInterval.push_back(Intervals[i]);
}
}
return tempInterval;
}
};
C++ 解法, 执行用时: 8ms, 内存消耗: 828KB, 提交时间: 2021-11-25
/**
* struct Interval {
* int start;
* int end;
* Interval(int s, int e) : start(start), end(e) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param Intervals Interval类vector
* @param newInterval Interval类
* @return Interval类vector
*/
vector<Interval> insertInterval(vector<Interval>& Intervals, Interval newInterval) {
// write code here
if(Intervals.empty()) {
Intervals.push_back(newInterval);
return Intervals;
}
//第一个左比new右大，直接在第一个前插入new
if((Intervals.begin())->start>=newInterval.end) {
if((Intervals.begin())->start>newInterval.end)
Intervals.insert(Intervals.begin(),newInterval);
else (Intervals.begin())->start=newInterval.start;
return Intervals;
}
if((Intervals.end()-1)->end<=newInterval.start) {
if((Intervals.end()-1)->end<newInterval.start)
Intervals.push_back(newInterval);//最后一个右比new左小，直接在最后插入
else (Intervals.end()-1)->end=newInterval.end;//最后一个右==new左，直接修改最后一个的右
return Intervals;
}
//最后一个的左<=new左，直接让最后一个的右=max(最后一个的右,new右)
if((Intervals.end()-1)->start<=newInterval.start) {
(Intervals.end()-1)->end=max((Intervals.end()-1)->end,newInterval.end);
return Intervals;
}
//最后一个的右<=new的右
if(newInterval.end>=(Intervals.end()-1)->end) {
if(newInterval.start<=(Intervals.begin())->start) {
Intervals.clear();
Intervals.push_back(newInterval);
}//如果第一个的左比new左大，直接清空原区间，插入new。
else {
vector<Interval>::iterator it=Intervals.end()-1;
while((*it).start>newInterval.start) --it;
(*it).end=newInterval.end;
Intervals.erase(it,Intervals.end());
}//从后往前循环找到第一个左比new左小的，然后让这个的右=new的右，后面的直接删掉
return Intervals;
}
vector<Interval>::iterator it=Intervals.begin();//it指向最后一个左比new左小的位置
while((*(it+1)).start<newInterval.start) ++it;//循环找到最后一个左比new左小的位置
if((*it).end>=newInterval.end) return Intervals;//1、如果it右比new右大，直接返回
vector<Interval>::iterator it2=it+1;
//2、it右<new左分三种情况
if((*it).end<newInterval.start) {
if((*(it2)).start<newInterval.end) {
while((*it2).end<newInterval.end) it2=Intervals.erase(it2);
if(newInterval.end>=(*it2).start) (*it2).start=newInterval.start;
else Intervals.insert(it2,newInterval);
}
else if((*(it2)).start==newInterval.end) {
(*it2).start=newInterval.start;
}
else {
Intervals.insert(it+1,newInterval);
}
}
//3、it右>=new左,分三种情况
else if((*(it)).end>=newInterval.start) {
if((*(it2)).start<newInterval.end) {
while((*it2).end<newInterval.end) it2=Intervals.erase(it2);
if(newInterval.end>=(*it2).start) (*it).end=(*it2).end,Intervals.erase(it2);
else (*it).end=newInterval.end;
}
else if((*(it2)).start==newInterval.end) {
(*it).end=(*it2).end;
Intervals.erase(it2);
}
else {
(*it).end=newInterval.end;
}
}
return Intervals;
}
};