在给定范围列表的情况下找到最大重叠范围的有效算法

Question

请考虑以下描述连续integer值范围的界面.

public interface IRange {
    int Minimum { get;}
    int Maximum { get;}

    IRange LargestOverlapRange(IEnumerable<IRange> ranges);
} 

我正在寻找一种有效的算法来找到给定IRange对象列表的最大重叠范围.下图简要概述了这个想法.顶部数字表示integer值,并用最小值和最大值|-----|表示IRange对象.我堆叠了IRange对象,以便解决方案易于可视化.

0123456789  ...                            N
|-------|   |------------|        |-----|
   |---------|    |---|
       |---|             |------------|
               |--------|  |---------------|
                              |----------|

这里,该LargestOverlapRange方法将返回:

                                  |---|

由于该范围总共有4个'重叠'.如果有两个IRange相同数量的重叠,我想返回null.

这是我尝试过的一些简要代码.

public class Range : IRange 
{

    public IRange LargestOverlapRange(IEnumerable<IRange> ranges) {           

        int maxInt = 20000;    

        // Create a histogram of the counts
        int[] histogram = new int[maxInt];
        foreach(IRange range in ranges) {
            for(int i=range.Minimum; i <= range.Maximum; i++) {
                histogram[i]++;
            }
        }

        // Find the mode of the histogram
        int mode = 0;
        int bin = 0;
        for(int i =0; i < maxInt; i++) {
            if(histogram[i] > mode) {
                mode = histogram[i];
                bin = i;
            }
        }

        // Construct a new range of the mode values, if they are continuous
        Range range;
        for(int i = bin; i < maxInt; i++) {
            if(histogram[i] == mode) {  
                if(range != null)
                    return null; // violates two ranges with the same mode   
                range = new Range();             
                range.Minimum = i;                     
                while(i < maxInt && histrogram[i] == mode)
                    i++;
                range.Maximum = i;                    
            }
        }

        return range;
    }

}

这涉及四个循环,如果不是更高则很容易为O(n ^ 2).是否有更有效的算法(速度方式)从其他范围列表中找到最大的重叠范围？

编辑

是的,O(n ^ 2)不正确,我正在考虑错误.它应该是O(N*M),正如评论中指出的那样.

编辑2

让我说明一些事情,值的绝对最小值和最大值integer将来自(0,20000).其次,平均数量IRange将在100的数量级.我不知道这是否会改变算法的设计方式.

编辑3

我在科学仪器(质谱仪)上实施该算法,其中数据处理的速度对数据质量是最重要的(更快的分析时间=在时间T中收集的更多光谱).固件语言(专有)仅具有数组[],并且不是面向对象的.我之所以选择C#是因为我在两种语言之间移植概念方面很不错,并认为为了SO社区的利益,一个好的答案会有更广泛的受众.

Answer 1

将范围列表转换为起点和终点列表.使用O(n log n)算法对列表进行排序.现在,您可以遍历列表并根据计数器的起点或终点递增或递减计数器,这将为您提供当前的重叠深度.