在C++中合并范围

Question

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

R _i = [r1 _i,r2 _i ](r1 _i <= r2 _i)

随后,一些范围重叠(部分或完全),因此需要合并.

我的问题是,用于合并这些范围的最佳算法或技术是什么.这种算法的示例或到执行这种合并操作的库的链接将是很好的.

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 - 将集合实现为一组间隔 - 合并相邻的间隔.
• 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)

这里是关于算法的复杂性:

加时间复杂性