发现线段工会在数轴上 [英] finding unions of line segments on a number line

问题描述

我公司拥有一批线在0到1000我在数轴上许多线段。所有线段'x1为> = 0和所有x2是＆其中; 1000所有x1和x2是整数。

I have a number-line between 0 to 1000. I have many line segments on the number line. All line segments' x1 is >= 0 and all x2 are < 1000. All x1 and x2 are integers.

我需要找到所有的线段的工会。

I need to find all of the unions of the line segments.

在此图像中，线段都采用了蓝色和工会都在红：

In this image, the line segments are in blue and the unions are in red:

是否有这种类型的问题？

Is there an existing algorithm for this type of problem?

推荐答案

如果该段没有动态变化，这是一个简单的问题。只是排序所有段通过左端，然后扫描排序的元素：

If the segments are not changed dynamically, it is a simple problem. Just sorting all the segments by the left end, then scanning the sorted elements:

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）的（扫描）。

The time complexity is O(nlogn) (sorting) + O(n) (scan).

如果该段插入动态删除，并且要随时查询工会，你需要一些更复杂的数据结构等的范围树。

If the segments are inserted and deleted dynamically, and you want to query the union at any time, you will need some more complicated data structures such as range tree.

这篇关于发现线段工会在数轴上的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！