计算整数范围的重叠次数

Question

我在这个算法上卡了很久。

假设有四个整数范围。每个范围都有一个起始值和一个结束值。

Range A: 0,5
Range B: 4,12
Range C: 2,10
Range D: 8,14

根据这些值，我想得到一个新集合，它计算出落在某个整数范围内的区间数量。其中每个区间都有起始值、结束值和计数值，生成类似于以下内容：

(Start, End, Count)
0,1,1   (Only 1 range (A) falls between 0 and 1 inclusive)
2,3,2   (2 ranges (A,C))
4,5,3   (3 ranges (A,B,C))
6,7,2   (2 ranges (B,C))
8,10,3  (3 ranges (B,C,D))
11,12,2 (2 ranges (B,D))
13,14,1 (1 range (D))

这个有意义吗？有什么好的方法来处理算法？

- Sam Washburn

---

你需要的算法取决于你的使用情况 - 你预计会处理多少范围和最大范围大小？ - Patashu

@Patashu 最大范围数量应该在数百到低千个之间，范围大小也应如此。 - Sam Washburn

如果您不需要记住哪些范围包含哪些数字，只需要知道覆盖它的范围数量，请创建一个索引为0...n（其中n是任何范围中最大的max）的数组，并为每个范围增加其覆盖的所有数组元素1。 - Patashu

请看这里 - http://jsfiddle.net/vsync/jrbb471h - vsync

@vsync 很酷。虽然那已经是将近3年前的事了。我甚至都不记得当时在写什么代码了。哈哈。 - Sam Washburn

我现在也在思考这个问题。 - vsync

Answer 1

您可以使用O(N ln N)的时间（用于排序），然后再花同样多的时间输出结果来解决此问题。如果数字范围很大，则O(N ln N)比在评论中建议的方法的O(M·N)更好（其中M=由范围覆盖的数字的总范围）。

将N个范围按Start值升序排列，以数组S为键。初始化一个空优先级队列P。将深度计数D初始化为零，并将当前“reach”初始化为R = S [0] .Start。

当S [i] .Start = R时，将S [i] .End推入P并推进i和D。当S [i] .Start> R时，生成元组（R，p.top，D）。弹出P到R，然后将D减少一并弹出P，同时P.top == R。

当i < N时，重复上述段落。

- James Waldby - jwpat7

---

更详细的解释，请参见区间树。 - Frank Sebastià

Answer 2

const ranges = {
  A: [10, 12],
  B: [20, 30],
  C: [29, 31],
  D: [15, 95],
  E: [195, 196]
};

let overlaps = {},
    keys = Object.keys(ranges),
    values = Object.values(ranges),
    i, j;

for (i = 0; i < values.length; i++)
  for (j = 0; j < values.length; j++)
    if (keys[i] !== keys[j] &&           // skip same item
        values[i][0] < values[j][1] &&   // overlap check
        values[j][0] < values[i][1])     // overlap check
      overlaps[keys[i]] = 1;

console.log( Object.keys(overlaps) )

- vsync

Answer 3

如果一个范围x与输入范围y相交，则为：

x.End >= y.Start AND y.End >= x.Start

所以，对于给定的输入，只需循环遍历您的范围集合，看哪些满足上述条件。

如果您给定的范围集合很少更改，并且比问题描述中提到的4个范围要大得多，则首先对其进行排序，以便更有效地搜索与您的输入相交的范围，而不是循环遍历所有范围。

如果给定的范围集合经常更改，则排序可能过于昂贵，此时最好每次都遍历所有范围。

- mbeckish