间隔范围插入并拆分为唯一范围

Question

寻找算法想法如何插入区间范围值，使其不会与现有区间重叠。

间隔范围排序从小到大 [[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）也欢迎伪代码实现。

Answer 1

in the actual code there is a differentiation between old interval ranges and new ranges after applying certain operation those ranges would be merged together. I wanted to split the question into smaller chunk so the merging part is left out.

Solely：直接合并到新的区间内，比人为拆分更容易。所以这就是我在下面提出的建议（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);
        }
    }
}

仅算法，省去了打包成 class 的设计工作，具有接受 begin/end 标记（而不是间隔）的便利函数，...

如果您打算使用的数据类型不提供后向访问器（C++：例如std::forward_list）：没问题，只需删除第二个if（包含(2)） ;那么，然而，b 可以是结束迭代器，所以你必须测试，如果测试成功，你可以在结束处插入。那时你很可能没有 'insert before'，所以你也需要分别跟踪 b 和后来的 e 的前辈......

间隔范围插入并拆分为唯一范围

Interval range insert with split into unique ranges

javascript

language-agnostic

algorithm

pseudocode