如何有效地重叠区间

Question

我需要您的帮助，我有一个问题(见图)，我假设有两个数组，每个数组包含具有不同长度和实际值的间隔，我需要了解如何有效地重叠这些间隔。

我是开放的想法，或书面理论或具体的算法，这将让我找到出路！我猜会以某种方式将其转化为波浪并与之重叠。

这很重要，这是为了我的论文。

举个例子，这里的数字更好地解释了这一点：

1. 阵列: 1-2，5-7，9-12
2. 阵列: 3-4，5-6，13-17

结果将是一个包含新间隔的数组。

第二间隔(阵列一和二)重叠。

结果阵列: 1-2，3-4，5-7，9-12，13-17

我在想“间隔树”，但我怎么把它们合并还不够。

​

​

提前感谢！

Answer 1

1)将所有的间隔放在一个数组中。

2)根据每个区间的下界对数组进行排序。

3)通过从最低下限到最高上限的间隔的循环：

( a)如果在此结束之前开始此间隔，则合并它们(删除第二个，并将其扩展为其上限)。

( b)重复，直到下一个间隔在这个间隔结束后开始。

4)重复，直到你到达最后一次间隔。

Answer 2

下面是python中的一个版本(版本2和3)：

def aggregate(data):
    data.sort()
    i = 0
    while i < len(data) - 1:
        while i < len(data) - 1 and data[i][1] >= data[i+1][0]:
            data[i] = (data[i][0], max(data[i][1], data[i+1][1]))
            data.pop(i+1)
        i += 1

if __name__ == '__main__':
    itervals = [(1,2), (5,7), (9,12), (3,4), (5,6), (13,17)]

    formatted = lambda vals: '[{}]'.format(', '.join('({}-{})'.format(
                                                   iterval[0], iterval[1])
                                                   for iterval in sorted(vals)))
    print(formatted(itervals))
    aggregate(itervals)
    print(formatted(itervals))

输出：

[(1-2), (3-4), (5-6), (5-7), (9-12), (13-17)]
[(1-2), (3-4), (5-7), (9-12), (13-17)]

注意:这改变了一个元组的列表。这是一个稍微通用的方法，可以通过更改行来处理可迭代性的列表：

data[i] = type(data[i])((data[i][0], max(data[i][1], data[i+1][1])))

或者，如果您知道您有一个可变可迭代的列表，则可以使用：

data[i][1] = max(data[i][1], data[i+1][1])

另一种可能比较容易理解的版本是：

def aggregate(data):
    if not data:
        return data

    inputs = sorted(data)
    result = [inputs[0]]

    for next0, next1 in inputs[1:]:
        last0, last1 = result[-1]
        if next0 <= last1:
            result[-1][1] = max(next1, last1)
        else:
            result.append([next0, next1])

    return result

请注意，此列表是为列表设计的。

Answer 3

#include <vector>
using namespace std;

struct INTERVAL {
    int a; 
    int b;
};

// v is a sorted vector of intervals (a<=b)
// i is an interval (a<=b) to be merged with v, 
vector<INTERVAL> merge(vector<INTERVAL>& v, INTERVAL& i)
{
    bool fMerged=false; // merged flag
    INTERVAL r=i; // merged interval
    vector<INTERVAL> out; // out vector
    vector<INTERVAL>::size_type k=0; // iterator 

    for(k=0; k<v.size(); ++k) { 
        if (fMerged || v[k].b < r.a) {          
            out.push_back(v[k]); // v[k] comes first
        } 
        else if (r.b<v[k].a) {
            out.push_back(r); // r comes first
            out.push_back(v[k]);
            fMerged=true; // copy rest;
        }
        else { // intervals overlap, merge into r
            r.a=min(v[k].a,r.a); 
            r.b=max(v[k].b,r.b);
        }
    }
    // interval not merged, append to vector
    if (!fMerged) out.push_back(r);
    return out;
}

这可能是一种方法