获取表示开始/结束的数字对，并删除重叠部分

Question

我有一个表示范围为[begin，end)的对数组。可以假定该数组已按“begin”字段排序。

我希望生成一个新的数组，删除所有重叠，并根据需要创建额外的对。

例如，假设数组包含以下对：

[1,3],[2,5],[7,15],[8,9],[12,19]

输出应如下所示：

[1,2],[2,3],[3,5],[7,8],[8,9],[9,12],[12,15],[15,19]

最终，输出数组不应包含任何重叠。

不超过O(m)的最优解决方案是什么，其中m是输出数组中所需的条目数？我想我在O(n^2)中看到了一种方法，其中n是输入数组中的条目数，但肯定有更好的方法。

最终的实现将在C++11中，使用成对的双精度向量，尽管伪代码解决方案很好。

编辑：

我感谢所有的回复，但我会礼貌地请求您不要发布任何依赖于特定框架或库的解决方案，除非这些框架是标准c++11的一部分。

Answer 1

首先，我将解决一个相关的问题；生成覆盖相同区域的合并间隔，而没有邻接或重叠。

遍历输入数组。从第一个元素开始。记录高水位(区间结束)和低水位(区间开始)。

继续前进。每个元素，如果它与区间重叠，则延伸高水位。如果不是，则输出高水位和低水位作为间隔，然后记录新的高水位和低水位。

这在输入上需要O(n)时间。

必须读取输入的每个元素，因为它们中的任何一个都可以从开始位置移动到结束位置并更改结果。所以这是最优的。

这会将间隔合并为您可以创建的最大的连续间隔；您希望保存原始间隔中的所有“边”或“接缝”。要解决您的规范，只需跟踪接缝(按顺序)，并在这些接缝处打破生成的间隔。“低”接缝总是会增加价值；高水位接缝可能不会。因此，一组有序的接缝应该是有效的。由于集合的原因，这是O(nlgn)。

// half open
struct interval {
    int lowater = 0;
    int highwater = 0;
    bool empty() const {
        return lowater == highwater;
    }

    friend std::ostream& operator<<( std::ostream& os, interval i ) {
        return os << "[" << i.lowater << "," << i.highwater << "]";
    }
};


template<class Range, class Out>
void build_intervals( Range&& in, Out out ) {
    std::optional<interval> current;
    std::set<int> seams;

    auto dump_interval = [&](interval i){
        if (i.empty()) return;
        *out = i;
    };
    auto dump_current = [&]{
        if (!current) return;

    //    std::cout << "Dumping " << *current << " with seams: {";
        for (int seam:seams) {
    //        std::cout << seam << ",";
            dump_interval({ current->lowater, seam });
            current->lowater = seam;
        }
    //    std::cout << "}\n";
        dump_interval( *current );
        current = std::nullopt;
        seams.clear();
    };
    for (auto&& e : in) {
        if (current && e.lowater <= current->highwater) {
            seams.insert(e.lowater);
            seams.insert(e.highwater);
    //        std::cout << "No gap between " << *current << " and " << e << "\n";
            current->highwater = (std::max)(e.highwater, current->highwater);
    //        std::cout << "Combined: " << *current << "\n";
            continue;
        }
        if (!current) {
    //        std::cout << "New current " << e << "\n";
        } else {
    //        std::cout << "Gap between " << *current << "  and " << e << "\n";
            dump_current();
        }
        current = e;
        seams.insert(e.lowater);
        seams.insert(e.highwater);
    }
    dump_current();
}

live example。