给出很多间隔[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 put ai first iff bi < bj
• if bi = bj, then put bi first iff ai < aj
• if ai = bj, then put ai 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 as minus running total of bs). 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屋！