algorithm - 重叠矩形的最大数量

Question

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

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) 的解决方案。