给定一组区间，发现其具有交点的最大数量的时间间隔 [英] Given a set of intervals, find the interval which has the maximum number of intersections

问题描述

给定一组区间，发现其具有交点的最大数目（不特定交叉点的长度）的时间间隔。因此，如果输入（1,6）（2,3）（4,11），（1,6）应返回。有人建议用区间树得到的O（nlogn）完成这件事，但我不明白如何构造并读取它的wiki页面后，使用间隔树。我相信它可以通过做某种排序和扫描算法来完成。如果间隔树是唯一的选择，请教育我如何构建/使用一个。谢谢你。

Given a set of intervals, find the interval which has the maximum number of intersections (not the length of a particular intersection). So if input (1,6) (2,3) (4,11), (1,6) should be returned. Some suggest to use Interval Tree to get this done in O(nlogn), but I did not understand how to construct and use the Interval Tree after reading its wiki page. I believe it can be done by doing some sort of sorting and scanning algorithm. If Interval tree is the only option, please educate me how to construct/use one. Thanks.

推荐答案

注意：大卫Eisenstat的算法比这更好的性能

一个简单的平面扫描算法将做到这一点 O（nlogn + M * N），其中 M 是交点与任何单个间隔的最大数量。

A simple plane-sweep algorithm will do this in O(nlogn + m*n), where m is the maximum number of intersections with any single interval.

排序区间端点。跟踪活动的节段。当到达开始点，增量的交点所有活动间隔计数，并设置新的时间间隔的交叉点计数，以活性间隔（不包括自身）的数目。当到达终点，从活动的时间间隔删除的间隔时间。

Sort the interval endpoints. Keep track of the active segments. When reaching a start point, increment the intersection counts of all active intervals, and set the new interval's intersection count to the number of active intervals (excluding itself). When reaching an end point, remove the interval from the active intervals.

这篇关于给定一组区间，发现其具有交点的最大数量的时间间隔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！