4

问题很简单，平面上有一些给定的一维线。我们需要找到至少有一行的空间的总大小。

让我用一个示例图像来讨论这个问题 -

森尼亚里奥 1

这可能是一个案例。或者

世纪 2

这可能是一个案例或类似的事情。

我知道这是Sweep Line Algorithm的一个基本问题。

但是互联网上没有适当的文档可以正确理解。

我拥有的最好的一个是Top Coder的博客，就在这里。

但目前尚不清楚如何实现它或如何进行模拟。

如果我愿意，我们可以用 2 个循环在 O(n^2) 中完成，但我不知道这个过程会如何。

还是有比 O(n log n) 更好的算法？

任何人都可以通过分享任何 Sudo 代码或模拟来帮助我吗？

如果 Sudo 代码或示例代码不可用，那么从我可以实现的地方进行模拟就足够了。

重新 计算重叠日期范围的问题不是我想要的，因为首先，它是 O(n^2)，所以这不是我想要的。它并没有像这个问题那样被完全描述。

4

5 回答 5

9

没有太多可用于此主题的信息。

所以，我正在与你分享我为你创建的算法和模拟，它也是O(n log n) !!!!!!

开始吧-

  1. 创建所有行动点的优先级列表（行动点是一条线的起点或终点）。PQ 的每一项都有 3 个元素（当前点、起点或终点、来自哪条线）。（如果我们使用Quick Short进行排序，则为O(n log n)操作）。
  2. 初始化一个用于存储当前活动行的向量。
  3. 初始化一个大小 = 行数 + 1 的数组（用于存储阴影长度的总和）。

数据结构

  1. 现在从PQ中删除一个项目并为该项目运行特定操作，如下图所述，您就完成了。

模拟 0

0

模拟人生 1

1

2

2

3

3

4

4

5

5

6

6

7

7

8

8

9

9

10

10

结尾

11

  1. 并一直这样做，直到 PQ 为空。

在您的情况下，找到从 1 到结尾的数组所有元素的总和（索引号 1 到 m），这就是您的答案。

但是使用这个算法和数组，你可以很容易地得到许多更复杂的问题答案，比如有 3 shadow = Arr 3的空间长度是多少等等。

现在的问题是order 是什么，对吧？

所以，排序 = O(n log n) 和清扫 = O(m) [m=没有动作点，所以 m

因此，总订单为 = O(n log n) + O(m) = O(n log n)

认为您可以轻松理解它，并且将对您和许多其他人有很大帮助。并认为您将能够轻松实现它。

于 2015-08-28T04:03:03.630 回答
1

这是您可以尝试的一种方法（在 C# 中。我没有测试过，所以请原谅拼写错误等；只需采用“想法”/策略）。

性能为 O(N log m)，其中 m 是您将创建的不相交“阴影”的数量。所以，最坏的情况（如果所有线段的阴影都不相交）你会有 O(N logN)，但是当你只有很少的阴影时，它本质上是 O(N)。

  public class LineSegment
  {
    public int Begin;
    public int End;
    // assumed to INCLUDE Begin but EXCLUDE End, so that
    // length = End-Begin

    public LineSegment Clone()
    {
      LineSegment clone = new LineSegment();
      clone.Begin=this.Begin;
      clone.End = this.End;
      return clone;
    }
  }

public int TotalShadow(LineSegment[] segments)
{
  // Class LineSegment has int members Begin and End, and Clone method to create a (shallow) Copy.
  // Can/should be adapted if we're dealing with LineSegments with double/float coordinates.

  // Easy special cases: no segements at all, or precisely one.
  int N = segments.Length;
  if (N == 0)
    return 0;
  else if (N == 1)
    return (segments[0].End - segments[0].Begin);

  // build a list of disjoint "shadows", cast onto the x-axis by all line segments together,
  // sorted by their "Begin" (leftmost coordinate).
  List<LineSegment> shadows = new List<LineSegment>();
  // Initialize with the first segment, for convenient iteration below.
  shadows.Add(segments[0].Clone());

  for (int k = 1; k < N; ++k) // start at #1: we handled #0 already.
  {
    // find its position (Begin) in relation to the existing shadows (binary search).
    int xBegin = segments[k].Begin;

    int jLow = 0;
    int xLow = shadows[jLow].Begin;

    int jHigh, xHigh;
    if (xBegin <= xLow)
      jHigh = jLow; // avoid any more binary searching below
    else
    {
      jHigh = shadows.Count - 1;
      xHigh = shadows[jHigh].Begin;
      if (xBegin >= xHigh)
        jLow = jHigh; // avoid any more binary searching below
    }

    while (jHigh - jLow > 1)
    {
      int jTry = (jLow + jHigh) / 2;
      int xTry = shadows[jTry].Begin;

      if (xTry <= xBegin)
        jLow = jTry;
      else
        jHigh = jTry;
    }

    // If it starts BEFORE "low" we create a new one: insert at jLow;
    // Elseif x falls INSIDE "low", we merge it with low;
    // ELSE we create a new shadow "between" low and high (as regards Begin)
    // In all cases we'll make sure jLow points to the applicable shadow (new or existing).
    // Next we'll check whether it overlaps with adjacent higher-lying shadows; if so: merge.
    if (xBegin < shadows[jLow].Begin)
      shadows.Insert(jLow, segments[k].Clone()); // jLow now points to the inserted item
    else if (xBegin <= shadows[jLow].End)
    { // merge: extend existing low if applicable.
      if (segments[k].End > shadows[jLow].End)
        shadows[jLow].End = segments[k].End;
    }
    else // if (xBegin > shadows[jLow].End)
      shadows.Insert(++jLow, segments[k].Clone()); // jLow increased to point to the inserted item.

   // Try to merge, starting at the next higher lying shadow.
    jHigh = jLow + 1;
    while (jHigh < N && shadows[jLow].End >= shadows[jHigh].Begin)
      jHigh++; // jHigh will point to the first one that we do NOT merge with.

    if (jHigh > jLow + 1) // any merges?
    {
      if (shadows[jHigh - 1].End > shadows[jLow].End)
        shadows[jLow].End = shadows[jHigh - 1].End; // set the appropriate End.

      for (int jRemove = jHigh - 1; jRemove > jLow; --jRemove)
        shadows.RemoveAt(jRemove); // Remove all shadaow-entries that we've merged with.
    }
  }

  // Wrap up.
  int shadowTotal = 0;
  foreach (LineSegment shadow in shadows)
    shadowTotal += (shadow.End - shadow.Begin);

  return shadowTotal;
}
于 2015-08-28T08:23:56.997 回答
0

这不是很复杂。

形成一个数组，在其中放置所有间隔端点横坐标，并带有一个标志，告诉它是起点还是终点。

越来越多地对数组进行排序。

然后在更新计数器的同时扫描数组：起点增加它，终点减少它。

请求的大小很容易从计数器从零切换到非零的值中找到，反之亦然。

由于排序（我认为无法避免），我认为不可能使它比 O(N Log(N)) 更快，除非数据允许线性时间排序（例如直方图排序）。

于 2015-08-28T08:46:27.360 回答
0

也许你可以比盲排序做得更好，使用以下从 MergeSort 派生的方案：

  • 假设您有两个非重叠间隔列表，按递增界限排序；

  • 执行 MergeSort 中的合并步骤（始终从每个列表移动到最近的边界），以计算区间的并集；

  • 根据两个列表中索引的奇偶性，您可以判断要发出哪个边界（将 AB 和 CDEF 与排序 ACBDEF 合并，输出将是 ADEF）。

这是一个线性时间操作。

配备此修改后的合并，您可以实现修改后的 MergeSort，它从单个间隔开始并递归地形成联合。最后，您会得到一个间隔列表，这些间隔将为您提供所需的大小。

在最坏的情况下，没有边界会消失并且过程仍然存在O(N Log(N))。但是当确实出现足够多的区间联合时，区间的数量会减少并且处理时间可以下降到线性O(N)。

于 2015-08-28T09:18:19.360 回答
0

制作一个结构数组/列表，其中包含段终点坐标X和+1起点-1属性和终点属性A。上）

按键排序数组X。O(NlogN)

初始化CurrCount为零，遍历数组，将A属性添加到CurrCount. 上）

您将获得CurrCount大于零（覆盖）和CurrCount零（未覆盖）的范围

于 2015-08-28T06:04:57.513 回答