给定一组区间，找出交叉点数最多的区间 [英] 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.

推荐答案

注意:David 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屋！