3

给定网格 L*C 中 N 个矩形 (N<=100.000) 的坐标（L 和 C 的范围可以从 0 到 1.000.000.000），我想知道网格中任意点重叠矩形的最大数量是多少。

所以我想我会使用一个扫描算法，对于按 x 值排序的每个事件（矩形的开始或结束），我会在我的结构中添加或删除一个间隔。

我必须使用树来保持间隔的最大重叠，并且能够添加和删除间隔。

当间隔（开始和结束）的值在 0 到 100.000 之间时，我知道如何做到这一点，但在这里这是不可能的，因为平面的尺寸是从 0 到 1.000.000.000。我怎样才能实现这样的树？

4

2 回答 2

3

如果您预先知道所有矩形的坐标，则可以使用“坐标压缩”。

由于您只有 10^5 个矩形，这意味着您最多有 2*10^5 个不同的x和y坐标。因此，您可以创建从这些坐标到 1 到 2*10^5 的自然数的映射（通过简单地对坐标进行排序）。然后你可以使用你已经知道的普通树作为新坐标。

这足以获得矩形的数量，但如果您还需要它们重叠的点，您还应该保持反向映射，以便您可以返回矩形的真实坐标。在一般情况下，答案将是一个矩形，而不仅仅是一个点。

于 2012-08-30T22:05:41.340 回答
2

使用区间树。您的情况有点复杂，因为您确实需要加权区间树，其中权重是该区间的开放矩形的数量。

于 2012-08-30T20:27:41.940 回答