algorithm - 在数轴上找到线段的并集

Question

我有一个介于 0 到 1000 之间的数轴。我在数轴上有很多线段。所有线段的 x1 >= 0，所有 x2 < 1000。所有 x1 和 x2 都是整数。

我需要找到线段的所有并集。

在此图像中，线段为蓝色，联合为红色：

是否有针对此类问题的现有算法？

Answer 1

您可以使用 marzullo 的算法（有关更多详细信息，请参阅 Wikipedia）。这是我写的一个 Python 实现：

def ip_ranges_grouping(range_lst):
    ##  Based on Marzullo's algorithm
    ##  Input: list of IP ranges
    ##  Returns a new merged list of IP ranges
    table = []
    for rng in range_lst:
        start,end = rng.split('-')
        table.append((ip2int(start),1))
        table.append((ip2int(end),-1))
    table.sort(key=lambda x: x[0])
    for i in range(len(table) - 1):
        if((table[i][0] == table[i+1][0]) and ((table[i][1] == -1) and (table[i+1][1] == 1))):
           table[i],table[i+1] = table[i+1],table[i]

    merged = []
    end = count = 0
    while (end < len(table)):
        start = end
        count += table[end][1]
        while(count > 0): # upon last index, count == 0 and loop terminates
            end += 1
            count += table[end][1]
        merged.append(int2ip(table[start][0]) + '-' + int2ip(table[end][0]))
        end += 1
    return merged

Answer 2

如果段没有动态改变，这是一个简单的问题。只需按左端对所有段进行排序，然后扫描已排序的元素：

struct Seg {int L,R;};

int cmp(Seg a, Seg b) {return a.L < b.L;}

int union_segs(int n, Seg *segs, Segs *output) {
  sort(segs, segs + n, cmp);
  int right_most = -1;
  int cnt = 0;
  for (int i = 0 ; i < n ; i++) {
    if (segs[i].L > right_most) {
      right_most = segs[i].R;
      ++cnt;
      output[cnt].L = segs[i].L;
      output[cnt].R = segs[i].R;
    }
    if (segs[i].R > right_most) {
      right_most = segs[i].R;
      output[cnt].R = segs[i].R;
    }
  }
  return cnt+1;
}

时间复杂度为 O(nlogn)（排序）+ O(n)（扫描）。

如果段是动态插入和删除的，想要随时查询并集，就需要一些比较复杂的数据结构，比如范围树。

Answer 3

考虑到段的坐标是有界 ([0, 1000]) 整数，您可以使用大小为 1000 的数组，初始化为零。然后，您遍历您的段集，并在该段覆盖的数组的每个单元格上设置 1。然后，您只需遍历数组即可检查 1 的连续序列。

---      -----
  ---  ---
1111100111111100

复杂性取决于段的数量，但也取决于它们的长度。

这是另一种方法，它也适用于浮点段。对段进行排序。然后，您只需遍历已排序的路段并比较每个相邻路段的边界。如果他们交叉，他们在同一个工会。