重叠矩形的最大数量 [英] Max number of overlapping rectangles
问题描述
我看过这个面试问题，但不知道如何解决：
给定N个矩形，求出最大重叠矩形数。
例如，对于由左下角和右上角点表示的矩形，[（1，1），（3，3）]，[（2，2），（4，4）]，[（1， 3），（2、4）]，[（2、2），（3、3）]，返回3，因为前两个矩形和最后一个矩形重叠。我可以想到一个时间复杂度为O（n ^ 2）的算法，但是应该有一个O（NlogN）的算法。
I have seen this interview question and don't have idea on how to it: Given N rectangles, find the maximum number of overlapping rectangles. For example, for rectangles represented by bottom left and top right points, [(1, 1), (3, 3)], [(2, 2), (4, 4)], [(1, 3), (2, 4)], [(2, 2), (3, 3)], return 3 because the first two and last one rectangles overlap. I can think of an algorithm of time complexity O(n^2) but there should be an algorithm of O(NlogN).
推荐答案
要找到最大重叠数，我们需要执行以下操作：
In order to find the number of maximum overlaps, we need to do as follow:
-
将每个矩形分成两段，打开和结束，例如，对于矩形[[0,0）（1,1）]->我们可以使用两个线段[[0,0）（0,1）]和[（1,0），（ 1,1）]表示。
Break each rectangle into two segments, open and end, for example, for rectangle [(0,0) (1,1)] -> we can use two segments [(0,0) (0,1)] and [(1,0), (1,1)] to represent it.
根据其x坐标对所有这些线段进行排序。
Sort all of those segments based on its x coordinate.
遍历这些段，并在维护段树的同时跟踪矩形：
Iterating through those segments, and while maintaining a segment tree to keep track of the rectangles:
-
如果该段是开放的，并且具有坐标（x，y1）（x，y2）->将段树中的段（y1，y2）增加一个。
If the segment is open and have the coordinate (x,y1) (x,y2) -> increase the segment (y1, y2) in the segment tree by one.
如果线段很近并且具有坐标（x，y1）（x，y2）->将线段树中的线段（y1，y2）减小1。
If the segment is close and have the coordinate (x,y1) (x,y2) -> decrease the segment (y1, y2) in the segment tree by one.
当我们遇到一个开放段（x，y1）（x ，y2），我们还检查了细分树（y1，y2）中存在多少个细分，这些数字中的最大值是最终结果。
When we encounter an open segment (x,y1) (x,y2), we also check how many segments are existing in (y1,y2) in the segment tree, the maximum value among those numbers are the final result.
请注意，段树中的每个添加/删除/搜索查询都是O（log n）->我们获得了O（n log n）解决方案。
Notice that each add/delete/search query in the segment tree is O(log n) -> we obtain an O(n log n) solution.
这篇关于重叠矩形的最大数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
