区间的并集

Question

我有一个表示区间的类。这个类有两个属性 "start" 和 "end"，类型为可比较类型。现在我正在寻找一种有效的算法来合并这样一组区间。

谢谢提前。

- drvj

Answer 1

按其中一个条件（例如，起始点）对它们进行排序，然后在通过列表时检查其（右侧）相邻项是否存在重叠。

class tp:
    def __repr__(self):
        return "(%d,%d)" % (self.start, self.end)

    def __init__(self, start, end):
        self.start = start
        self.end = end


s = [tp(5, 10), tp(7, 8), tp(0, 5)]
s.sort(key=lambda self: self.start)
y = [s[0]]
for x in s[1:]:
    if y[-1].end < x.start:
        y.append(x)
    elif y[-1].end == x.start:
        y[-1].end = x.end

- geocar

---

我认为最后一个 elif 语句应该寻找重叠，而不一定是严格相等；然后最终的赋值需要采用 y[-1].end 和 x.end 中较大的一个。例如，参考以下代码：s=[tp(1,4),tp(6,8),tp(7,10)] - Noah

Answer 2

使用扫描线 算法。基本上，您对列表中的所有值进行排序（同时保留每个项的区间开始或结束状态）。此操作的时间复杂度为O(n log n)。然后在排序后的项目上进行单遍循环并计算区间O(n)。

O(n log n) + O(n) = O(n log n)

- Mehrdad Afshari

Answer 3

原来这个问题已经被解决了，而且已经有很多次了——在不同的水平上，使用不同的术语：http://en.wikipedia.org/wiki/Interval_tree，http://en.wikipedia.org/wiki/Segment_tree，还有“RangeTree”（由于OP的问题涉及大量间隔，这些数据结构非常重要）。

---

就我的Python库选择而言：

• 从测试中发现，最完整且最新的Python库是SymPy中的“Interval”和“Union”类（非过时）：请参见http://sympystats.wordpress.com/2012/03/30/simplifying-sets/。

• 另一个看起来不错的选择是Banyan，它的性能更高，但功能较少（例如不能删除浮点范围）：https://pypi.python.org/pypi/Banyan

最后：在SO上搜索IntervalTree、SegmentTree、RangeTree等，你会找到更多答案和技巧。

- Matt S.

Answer 4

地理车辆算法在以下情况下会失败：

s=[tp(0,1),tp(0,3)]

我不是非常确定，但我认为这是正确的方式：

class tp():
    def __repr__(self):
        return '(%.2f,%.2f)' % (self.start, self.end)
    def __init__(self,start,end): 
        self.start=start
        self.end=end
s=[tp(0,1),tp(0,3),tp(4,5)]
s.sort(key=lambda self: self.start)
print s
y=[ s[0] ]
for x in s[1:]:
    if y[-1].end < x.start:
        y.append(x)
    elif y[-1].end == x.start:
        y[-1].end = x.end
    if x.end > y[-1].end:
        y[-1].end = x.end
print y

我也实现了减法：

#subtraction
z=tp(1.5,5) #interval to be subtracted
s=[tp(0,1),tp(0,3), tp(3,4),tp(4,6)]

s.sort(key=lambda self: self.start)
print s
for x in s[:]:
    if z.end < x.start:
        break
    elif z.start < x.start and z.end > x.start and z.end < x.end:
        x.start=z.end
    elif z.start < x.start and z.end > x.end:
        s.remove(x)
    elif z.start > x.start and z.end < x.end:
        s.append(tp(x.start,z.start))
        s.append(tp(z.end,x.end))
        s.remove(x)
    elif z.start > x.start and z.start < x.end and z.end > x.end:
        x.end=z.start
    elif z.start > x.end:
        continue

print s

- osolmaz

Answer 5

将所有点排序。然后遍历列表，对于“起始”点增加计数器，对于“结束”点减少计数器。如果计数器达到0，则它确实是联合区间中的一个端点。

计数器永远不会变为负数，并且在列表末尾达到0。

- user66363

Answer 6

在C++中查找区间并集的总和

#include <iostream>
#include <algorithm>

struct interval
{
    int m_start;
    int m_end;
};

int main()
{
    interval arr[] = { { 9, 10 }, { 5, 9 }, { 3, 4 }, { 8, 11 } };

    std::sort(
        arr,
        arr + sizeof(arr) / sizeof(interval),
        [](const auto& i, const auto& j) { return i.m_start < j.m_start; });

    int total = 0;
    auto current = arr[0];
    for (const auto& i : arr)
    {
        if (i.m_start >= current.m_end)
        {
            total += current.m_end - current.m_start;
            current = i;
        }
        else if (i.m_end > current.m_end)
        {
            current.m_end = i.m_end;
        }
    }

    total += current.m_end - current.m_start;
    std::cout << total << std::endl;
}

- tcb