5

私はかなり長い間、このアルゴリズムに悩まされてきました。

整数の範囲が 4 つあるとします。各範囲には、開始値と終了値があります。

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

これらの値から、int の特定の範囲に含まれる範囲の数をカウントする新しいセットを取得したいと考えています。これらにはそれぞれ 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

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 に答える