5

我已经被这个算法难住了很久。

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

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

从这些值中，我想得到一个新的集合，它计算落在特定整数范围内的范围数。其中每一个都将具有 Start、End 和 Count 值，产生如下内容：

(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))

那有意义吗？什么是处理算法的好方法？

4

3 回答 3

3

您可以在 O(N ln N) 时间（用于排序）中解决此问题，然后在相同的时间内输出结果。如果数字范围很大，则 O(N ln N) 优于注释中建议的方法的 O(M·N) 时间（其中 M = 范围所涵盖的数字的总范围）。

将 N 个范围按升序排序，以 Start 值为键，例如在数组 S 中。初始化一个空的优先级队列 P。将深度计数 D 初始化为零，当前“范围”为 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 减 1 并在 P.top==R 时弹出 P。

重复以上段落i<N。

于 2013-06-17T00:19:20.603 回答
1 

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) )

于 2016-03-30T14:55:38.793 回答
0

如果满足以下条件，则范围 x 与输入范围 y 相交：

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

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

如果您给定的范围集合不经常更改，并且您的范围集合比您在问题描述中所述的 4 大得多，那么首先对它们进行排序，以便您可以更有效地搜索与您的输入相交的范围，而不是遍历所有这些。

如果给定的范围集合经常变化，那么排序可能过于昂贵，那么每次循环遍历所有范围会更聪明。

于 2013-06-17T01:05:47.113 回答