c++ - 取代表开始/结束的数字对，并删除重叠

Question

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

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

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

[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 中，使用 double 对的 vector ，尽管伪代码解决方案很好。

编辑:

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

Answer 1

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

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

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

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

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

---

这会将间隔合并为您可以创建的最大的连续间隔；您想要保存原始间隔中的所有“边缘”或“接缝”。要解决您的规范，只需跟踪接缝(按顺序)并打破这些接缝处生成的间隔。 “低水位”接缝的值(value)总是会增加；高水位接缝可能不会。所以一组有序的接缝应该可以工作。由于集合的原因，这是 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 .