合并 C++ 中的范围

Question

我有一个随机排序的唯一封闭范围 R₀...R_n-1 列表，其中

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

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

我的问题是，用于合并此类范围的最佳算法或技术是什么。此类算法的示例或执行此类合并操作的库的链接会很棒。

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);

Answer 2

Boost.Icl 可能是对你有用。

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

• Interval_set — 将一组实现为一组间隔 - 合并相邻的间隔。
• split_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)

以及这里关于他们算法的复杂性：

加法的时间复杂度< /a>

Answer 3

一个简单的算法是：

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

Answer 4

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

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

Answer 5

杰思罗的回答有一个错误。
应该是

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

Answer 6

我的算法不使用额外的空间，而且也是轻量级的。我使用了2-pointer方法。 '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”的公共类或结构。
快乐编码:)

Answer 7

我知道这距离最初接受的答案已经过去很长时间了。但在
c++11 中，我们现在可以通过以下方式

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

在 O(n) 比较中构造优先级队列。

请参阅 https://en.cppreference.com/w/cpp/container/优先队列/优先队列
了解更多详情。

因此我们可以在 O(n) 时间内创建一个优先级队列（最小堆）。在 O(1) 时间内获取最低间隔并在 O(log(n)) 时间内将其弹出。
所以总体时间复杂度接近 O(nlog(n) + 2n) = O(nlogn)