在C++中合并区间

Question

我有一组随机排序的唯一封闭区间 R₀...R_n-1，其中

R_i = [r1_i, r2_i] (r1_i <= r2_i)

随后，一些范围重叠（部分或完全），因此需要合并。

我的问题是，用于合并这些范围的最佳算法或技术是什么。提供执行此合并操作的算法示例或链接到库的示例将非常有用。

- Rikardo Koder

Answer 1

你需要做的是：

1. 按字典顺序排序项，其中范围键为 [r_start, r_end]

2. 迭代排序后的列表并检查当前项是否与下一项重叠。如果它们重叠，则将当前项扩展为 r[i].start，r[i+1].end，然后转到下一个项目。如果不重叠，则将当前项添加到结果列表中并移动到下一项。

以下是示例代码：

    vector<pair<int, int> > ranges;
    vector<pair<int, int> > result;
    sort(ranges.begin(),ranges.end());
    vector<pair<int, int> >::iterator it = ranges.begin();
    pair<int,int> current = *(it)++;
    while (it != ranges.end()){
       if (current.second > it->first){ // you might want to change it to >=
           current.second = std::max(current.second, it->second); 
       } else {
           result.push_back(current);
           current = *(it);
       }
       it++;
    }
    result.push_back(current);

- jethro

---

这种方法的总复杂度是否为O(nlogn) {基本上是排序复杂度+ N的1次线性扫描}？ - Rikardo Koder

根据空间大小，如果值适合使用基数排序而不是快速排序，则可能更有效。 基数排序的时间复杂度为O(kn)，其中k是键空间的大小。 - BeMasher

你的算法如何处理这种情况：当r[i].end + 1 == r[i+1].start时？实际上，这些范围也可以合并。 - abyss.7

Answer 2

Boost.Icl 可能对您有用。

该库提供了一些模板，您可以在您的情况下使用：

• interval_set —— 将集合实现为区间集 - 合并相邻的区间。
• separate_interval_set —— 将集合实现为区间集 - 保留相邻的区间分离。
• split_interval_set —— 将集合实现为区间集 - 在插入重叠区间时进行拆分。

这里有一个 示例，演示如何使用该库合并区间：

interval<Time>::type night_and_day(Time(monday,   20,00), Time(tuesday,  20,00));
interval<Time>::type day_and_night(Time(tuesday,   7,00), Time(wednesday, 7,00));
interval<Time>::type  next_morning(Time(wednesday, 7,00), Time(wednesday,10,00));
interval<Time>::type  next_evening(Time(wednesday,18,00), Time(wednesday,21,00));

// An interval set of type interval_set joins intervals that that overlap or touch each other.
interval_set<Time> joinedTimes;
joinedTimes.insert(night_and_day);
joinedTimes.insert(day_and_night); //overlapping in 'day' [07:00, 20.00)
joinedTimes.insert(next_morning);  //touching
joinedTimes.insert(next_evening);  //disjoint

cout << "Joined times  :" << joinedTimes << endl;

以及该算法的输出：

Joined times  :[mon:20:00,wed:10:00)[wed:18:00,wed:21:00)

关于他们算法的复杂性，可以参考以下链接：

加法的时间复杂度

- user184968

Answer 3

一个简单的算法如下：

• 按起始值对范围进行排序
• 从开头到结尾迭代范围，每当您发现一个与下一个重叠的范围时，将它们合并

- sth

---

不必进行排序，可以使用std::priority_queue，类似于扫描线方法吗？ - Rikardo Koder

由于您只想从最小到最大遍历它们，因此 std::priority_queue 应该可以胜任，但我认为它不会比排序更快/...。毕竟，您按顺序遍历所有项目，因此最终它们会被排序。 - sth

@Rikardo 优先队列只有在项目随时间到达时才有帮助。如果您已经拥有它们，只需对它们进行排序即可。最佳的优先队列和排序都是O(nlogn)（优先队列是n个插入，每个插入的复杂度为O(logn)），但排序性能更好且开销较小。 - Jim Balter

@JimBalter，您能否看一下我下面的答案并告诉我您的意见？ - the_interest_seeker

Answer 4

O(n*log(n)+2n):

• 建立一个映射关系 r1_i -> r2_i
• 对r1_i进行快速排序
• 遍历列表，为每个r1_i值选择最大的r2_i值
• 使用该r2_i值，可以跳过所有比r2_i小的后续r1_i值

- Bernd Elkemann

---

只是一个小点：O(nlog(n) + 2n) = O(nlog(n) + n) = O(n*log(n)) - andand

当然。但是（虽然在理论上不是这样），在实践中这些差异是显著的。 - Bernd Elkemann

在实践中说有差别是没有意义的，因为大O表示法是一个理论上定义的概念，根据其定义，O(nlogn+2n) = O(nlogn)。 - Jim Balter

@Jim Balter：我同意 andand 的观点，理论上没有区别！但是说“在实践中有所不同”并不是毫无意义的。在实践中，实践就是一切，而那些在理论上没有区别的大O符号可能会彻底毁掉你！ - Bernd Elkemann

@BeMasher 很高兴听到这个消息！我看了一下，但我还没有学过Go，所以我对它没什么可说的。 - Bernd Elkemann

Answer 5

jethro的回答有误。应该是

if (current.second > it->first){
    current.second = std::max(current.second, it->second);        
} else { 

- user515430

---

这应该是对Jethro的回答进行编辑，而不是单独的回答。 - Brian

Answer 6

我的算法不使用额外的空间，而且非常轻量级。我使用了2指针方法。'i'不断增加，而'j'跟踪正在更新的当前元素。 这是我的代码：

bool cmp(Interval a,Interval b)
 {
     return a.start<=b.start;
 }
vector<Interval> Solution::insert(vector<Interval> &intervals, Interval newInterval) {
    int i,j;
    sort(intervals.begin(),intervals.end(),cmp);
    i=1,j=0;
    while(i<intervals.size())
    {
        if(intervals[j].end>=intervals[i].start)  //if overlaps
        {
            intervals[j].end=max(intervals[i].end,intervals[j].end); //change
        }
        else
        {
            j++;
            intervals[j]=intervals[i];  //update it on the same list
        }
        i++;
    }
    intervals.erase(intervals.begin()+j+1,intervals.end());
    return intervals;
}

Interval可以是一个具有数据成员“start”和“end”的公共类或结构体。 编码愉快 :)

- Prateek Oraon

Answer 7

我知道这是原始答案被接受后很长一段时间。但在c++11中，我们现在可以按以下方式构造priority_queue

priority_queue( const Compare& compare, const Container& cont )

在O(n)次比较中。

请参见https://en.cppreference.com/w/cpp/container/priority_queue/priority_queue以获取更多详细信息。

因此，我们可以在O(n)时间内创建一对的priority_queue（最小堆）。在O(1)时间内获取最低间隔，并在O(log(n))时间内弹出它。因此，总时间复杂度接近于O(nlog(n) + 2n) = O(nlogn)

- the_interest_seeker