给出很多间隔[ai,bi],找到一个与最大间隔数相交的间隔 [英] giving lots of intervals [ai, bi], find a interval which intersect with the most number of intervals
问题描述
给出许多间隔[ai,bi], 找到与最多间隔数相交的间隔. 我们可以用O(nlogn)或更好的方式做到这一点吗?我只能想到一种n ^ 2的方法.
Given lots of intervals [ai, bi], find the interval that intersects the most number of intervals. Can we do this in O(nlogn) or better? I can think only of a n^2 approach.
推荐答案
假定间隔指定为(a1,b1), ..., (an,bn)
.制作一个长度为2n
的排序数组,其中领带被打破
Suppose the intervals are given as (a1,b1), ..., (an,bn)
. Make a sorted array of length 2n
where ties are broken by
- 如果
ai = aj
,则将ai
首先放在bi < bj
- 如果
bi = bj
,则将bi
首先放在ai < aj
- 如果
ai = bj
,则先放置ai
- if
ai = aj
, then putai
first iffbi < bj
- if
bi = bj
, then putbi
first iffai < aj
- if
ai = bj
, then putai
first
将每个点标记为a
或b
(为此,可以保留长度为2n
的二进制数组).遍历数组,跟踪有多少间隔触摸给定点(连续运行a
s减去连续运行b
s).遇到的最大次数是在重叠最多的时间间隔内发生的.
Mark each point as an a
or a b
(maybe keep a binary array of length 2n
to do this). Walk through the array(s) keeping track of how many intervals touch the given point (running total of a
s minus running total of b
s). The maximum number encountered happens at the interval with the most overlap.
由于间隔的排序,这是O(n log n)
.
This is O(n log n)
due to the sorting of the intervals.
这篇关于给出很多间隔[ai,bi],找到一个与最大间隔数相交的间隔的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!