给定一组间隔,找到具有最大交叉点数的间隔

Question

给定一组间隔,找到具有最大交叉点数的间隔(不是特定交叉点的长度).因此,如果输入(1,6)(2,3)(4,11),则应返回(1,6).有人建议使用Interval Tree在O(nlogn)中完成这项工作,但是在阅读其wiki页面后我不明白如何构造和使用Interval Tree.我相信它可以通过做某种排序和扫描算法来完成.如果Interval树是唯一的选项,请教我如何构建/使用一个.谢谢.

Answer 1

不要使用间隔树.为每个间隔端点创建一个事件,以便每个间隔都有一个开始事件和一个停止事件.按顺序处理这些事件.(如果测量零交点计为交点,则在停止之前开始订单,否则在开始之前停止.)

将间隔C从间隔初始化为数字.初始化开始计数s = 0并且停止计数t = 0.要处理间隔i的开始事件,设置s = s + 1然后设置C(i)= - (t + 1).要处理间隔i的停止事件,请设置t = t + 1,然后设置C(i)= C(i)+ s.

最后,C将间隔映射到它们的交叉点计数.由于排序,该算法为O(n log n); 如果可以通过相当标准的计算几何技术添加和比较端点,则运行时间是最佳的.

Answer 2

注意:David Eisenstat的算法比这个算法具有更好的性能.

一个简单的平面扫描算法将执行此操作O(nlogn + m*n),其中m是任何单个间隔的最大交叉点数.

对间隔端点进行排序.跟踪活动细分.到达起点时,增加所有活动间隔的交点计数,并将新间隔的交点计数设置为活动间隔数(不包括自身).到达终点时,从活动间隔中删除间隔.