从一组范围中查找最常见的数字 -

Question

问题如下: -

给你N个不同大象的生命时间,表示为一对整数.

恩.[5,10] [6,15] [2,7]意味着,一只大象从5年级到10年级生活.第二只大象从6年级到15年级,依此类推.

您可以假设大象最多只能活M年.(不是问题的一部分,但我们可能需要它来表示算法的复杂性.)

根据这些数据,找出最大数量的大象居住的年份.任意解决关系.

我已经尝试了几种方法,但没有任何实质性的东西可以打败天真的解决方案的复杂性.天真的解决方案是: -

1. Maintain an array(call it ctr).
2. For every set you encounter, 
    increment all values of ctr in that range.
3. Once you have traversed all sets, 
    find the index with the highest value in ctr.

很容易看出复杂性将是O(N*M).

有人能提供更好的解决方案吗？

另一个问题是:是否存在可以在O(1)时间内更改值范围的数据结构？在数组中,要修改k个元素,您显然需要O(k)时间.还有什么更好的？

Answer 1

将范围的左端视为+1大象活着,并将范围的右端视为-1大象活着.将这些+1和-1标记放在数字行上,然后在数字行上从左到右按顺序排列.当您走数字线时,跟踪当前活着的大象数量(只需加上+1和-1),然后根据活着的大象和相应的年份来检查它.然后你有一个很好的O(n log n)时间解决问题的方法.

请注意,您必须要小心谨慎,以便在当前年份的+ 1s之前处理-1s,或者仅在处理给定年份内的所有数据后更新最大值.