提问人：Risto Novik 提问时间：1/9/2019 最后编辑：Risto Novik 更新时间：1/10/2019 访问量：244
间隔范围插入，拆分为唯一范围
Interval range insert with split into unique ranges
问：
寻找如何插入间隔范围值的算法思路，使其不会与现有间隔重叠。
间隔范围按从小到大排序 [[0， 1]， [3， 5]]。
现在插入间隔范围 [0， 7] 到 [[0， 1]， [3， 5]] -> [[0， 1]， [1， 3]， [3， 5]， [5， 7]] -> 生成两个新范围，其他保持不变。
这是另一个示例，将范围 [-3， 5] 插入到 [[0， 1]， [6,7]] -> [[-3， 0]， [0， 1]， [1， 5]， [6， 7]]
所有编程语言（尤其是 JavaScript）也欢迎伪代码实现。
答：
1赞
Aconcagua
1/9/2019
#1
在实际代码中，旧间隔范围和新范围之间存在差异，在应用某些操作后，这些范围将合并在一起。我想将问题分成更小的块，以便省略合并部分。
唯一：直接合并到新的区间中更容易，而不是人为地拆分它。这就是我在下面提出的建议（C++）：
using DataType = /* whatever appropriate; double, int, unsigned int, ...*/;
using Interval = std::pair<DataType, DataType>;
std::vector<Interval> intervals;
void insert(Interval x)
{
if(intervals.empty() || x.second < intervals.front().first)
{
intervals.insert(intervals.begin(), x); // (1)
}
else if(x.first > intervals.back().second)
{
intervals.push_back(x); // (2)
}
else
{
auto b = intervals.begin();
while(b->second < x.first)
{
std::advance(b, 1);
}
// cannot be END iterator, otherwise would have been caught by (2)
if(x.second < b->first)
{
// this is a new interval in between std::prev(b) and (b)
intervals.insert(b, x);
}
else
{
// b is overlapping with x!
if(b->first > x.first)
{
b->first = x.first;
}
auto e = std::next(b);
while(e != intervals.end() && e->first <= x.second)
{
std::advance(e, 1);
}
// e is the first interval NOT overlapping with x!
auto l = std::prev(e);
b->second = std::max(x.second, l->second);
// drop all subsequent intervals now contained in b (possibly none)
intervals.erase(std::next(b), e);
}
}
}
仅算法，省去了打包到类中的设计工作，具有接受开始/结束标记（而不是间隔）的便利功能，...
如果您打算使用的数据类型没有提供反向访问器（C++：例如）：没问题，只需删除第二个（包含）;但是，可以是 end 迭代器，因此您必须测试 for，如果测试成功，则可以在 end 处插入。那时你很可能没有“插入”，所以你也需要分别跟踪 b 和后来的 e 的前辈......std::forward_listif(2)b
评论