c# - 给定范围列表找到最大重叠范围的有效算法

Question

考虑以下描述连续范围的 integer 值的接口(interface)。

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 内收集更多光谱)。固件语言(专有)只有 arrays[] 并且不是面向对象的。我选择 C# 是因为我擅长在两种语言之间移植概念，并且认为为了 SO 社区的利益，一个好的答案会有更广泛的受众。

Answer 1

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