最大重叠矩形的数量

Question

我看到了这个面试问题，但不知道如何解决: 给定N个矩形，请找出最大数量的重叠矩形。 例如，对于由左下和右上点表示的矩形，[(1, 1), (3, 3)], [(2, 2), (4, 4)], [(1, 3), (2, 4)], [(2, 2), (3, 3)]，返回3，因为前两个和最后一个矩形有重叠。我能想到的时间复杂度为O(n^2)的算法，但应该有一种O(NlogN)的算法。

- thinking_water

---

先发布您的解决方案，然后再寻求优化帮助。 - Samuel Neff

我想不出一个O(NlogN)的解决方案（但我不是算法专家...）。我能想到一些替代方法来做这件事，但不一定比你的O(n^2)暴力解决方案好。除了你提供的示例数据之外，我会询问面试官输入数据通常会是什么样子的？例如，N有多大？矩形有多大？是[(1,1),(3,3)]这样大小还是[(1000,1000),(30000000,30000000)]这样的大小？ - Faraway

请查看Lucanus Simonson的polygon包算法。他的实现是C++ BOOST库的一部分。他开发了基于点的多边形微积分，将基本布尔运算（例如交集）降低到线性时间。这应该有所帮助，尽管我还没有说服自己有一个简单的迭代来利用它来实现所需的解决方案。 - Prune

你需要使用一些特殊的数据结构，比如Fenwick树或线段树，才能实现O(n log n)的时间复杂度。你知道它们吗？ - Pham Trung

线段树可以，你能简要解释一下这个想法，或者给我一些实现O(nlogn)时间复杂度的参考资料吗？ - thinking_water

Answer 1

为了找到最大重叠数，我们需要按照以下步骤进行：

• 将每个矩形分成两个线段：起点和终点，例如对于矩形[(0,0)(1,1)] -> 我们可以使用两个线段[(0,0)(0,1)]和[(1,0),(1,1)]来表示它。

• 基于其x坐标对所有线段进行排序。

• 通过这些线段进行迭代，并同时维护一个线段树来跟踪矩形：

  • 如果该线段是开放的并且具有坐标(x,y1) (x,y2) -> 则将线段树中的线段(y1, y2)增加一。

  • 如果该线段是关闭的并且具有坐标(x,y1) (x,y2) -> 则将线段树中的线段(y1, y2)减少一。

• 当我们遇到一个开放线段(x,y1) (x,y2)时，我们还要检查线段树中存在多少线段位于(y1,y2)中，其中最大值即为最终结果。

请注意，每个线段树中的添加/删除/搜索查询都是O(log n) -> 我们可以得到一个O(n log n)的解决方案。

- Pham Trung

---

谢谢，解释清晰且非常有帮助。 - thinking_water

针对这个问题，如何创建线段树？ - user3787291

如何根据上述逻辑创建线段树？ - Neel Shah

Answer 2

按照要求，我的O(N^2)算法如下：

1. 将底部和顶部边缘的所有y轴值进行排序并去重，例如，在本例中，我们会得到(1, 2, 2, 3, 3, 4)。此步骤需要(NlogN)的时间复杂度。对于每个值，我们还需要记录它所属的矩形。

2. 获取每个矩形左侧和右侧边缘的所有x轴值（每个有2N个值），例如，在本例中，我们会得到(1, 2, 3, 4)。对于每个x值，我们想象创建一个通过(x,0)的垂直线。

3. 对于每条垂直线，迭代第一步中排序的所有值，计算当前垂直线上重叠的矩形的最大数量。我们可以通过扫描线算法在O(N)的时间内完成（在我们的示例中，当值为1时，有1个矩形，然后转到值为2，添加了两个矩形，因此有3个矩形重叠，在值3处，添加了一个矩形，另一个离开了，有2个矩形重叠）。因此，总共需要O(N^2)的时间复杂度。

- thinking_water

Answer 3

这可能是一个更清晰的答案

使用扫描线算法，可以在O(n^2)的时间复杂度内解决这个问题。 使用一条垂直于x轴的扫描线从左到右扫描所有矩形。

假设矩形i的左边界为x1，右边界为x2i。

当扫描线遇到x1时，进入事件并激活矩形i。

当扫描线遇到x2时，退出事件，并移除矩形i的激活状态。

对于每个事件，遍历所有矩形以确定哪些矩形是激活的。 然后将这些矩形在y轴上的投影视为一个区间，并使用差分数组找到重叠区间的最大数量。

当扫描线移动到最右端时，找到答案。

这里有一个具体问题，并且实现如下：

class Solution {
public:
  int fieldOfGreatestBlessing(vector<vector<int>>& forceField) {
    vector<pair<long long, pair<int, int>>> xevents;
    vector<int> alive(forceField.size());
    for (int i = 0; i < forceField.size(); i++) {
      auto& v = forceField[i];
      xevents.push_back(make_pair((long long)v[0] * 2 - v[2], make_pair(-1, i)));
      xevents.push_back(make_pair((long long)v[0] * 2 + v[2], make_pair(1, i)));
    }
    sort(xevents.begin(), xevents.end());
    int maxC = 0;
    for (auto& v : xevents) {
      if (v.second.first == -1) alive[v.second.second] = 1;
      else alive[v.second.second] = 0;
      vector<pair<long long, pair<int, int>>> yevents;
      for (int i = 0; i < forceField.size(); i++) {
        if (!alive[i]) continue;
        auto& v = forceField[i];
        yevents.push_back(make_pair((long long)v[1] * 2 - v[2], make_pair(-1, i)));
        yevents.push_back(make_pair((long long)v[1] * 2 + v[2], make_pair(1, i)));
      }
      if (yevents.size() == 0) {
        continue;
      }
      sort(yevents.begin(), yevents.end());
      int c = 0;
      for (auto& v : yevents) {
        if (v.second.first == -1) {
          ++c;
          if (c > maxC) {
            maxC = c;
          }
        }
        else {
          --c;
        }
      }
    }
    return maxC;
  }
};

来自

- Kargath

Answer 4

1. 按1x、y1、x2、y2的顺序对reactgales进行排序
2. 然后您需要遍历列表，并仅检查下一个矩形的左上角坐标是否位于先前矩形之一内。
3. 如果是，则重叠

"公式": CR = 要检查的当前矩形 R = 先前的矩形（将其添加到循环中）

cr.x1 >= r.x1 && cr.x1 < r.x2 && cr.y1 >= r.y1 && cr.y1 < r.y2

如果您有兴趣使用.Net解决方案 我甚至添加了额外的矩形

List<StackOverflowAnswers.Rectangle> _rectangles = new() { new() { x1 = 1, y1 = 1, x2 = 3, y2 = 3 },
new() { x1 = 2, y1 = 2, x2 = 4, y2 = 4 },
new() { x1 = 1, y1 = 3, x2 = 2, y2 = 4 },
new() { x1 = 2, y1 = 2, x2 = 3, y2 = 3 },
new() { x1 = 4, y1 = 1, x2 = 5, y2 = 2 },
new() { x1 = 1, y1 = 1, x2 = 2, y2 = 2 }
};

int _overlaps = 0;

_rectangles = _rectangles.OrderBy(r => r.x1).ThenBy(r => r.y1).ThenBy(r => r.x2).ThenBy(r => r.y2).ToList();
StackOverflowAnswers.Rectangle cr;
for (int i = 1; i<_rectangles.Count;i++)
{
    cr = _rectangles[i];
    _rectangles.GetRange(0,i).ForEach(r => _overlaps += (cr.x1 >= r.x1 && cr.x1 < r.x2 && cr.y1 >= r.y1 && cr.y1 < r.y2) ? 1:0);
}

Console.WriteLine("Overlaps: " + _overlaps);

- Frederik van Lierde