2

重複する範囲の配列があります:

var ranges = [{
    "from": 0,
    "to": 100
}, {
    "from": 50,
    "to": 200
}, {
    "from": 0,
    "to": 100
}, {
    "from": 70,
    "to": 200
}, {
    "from": 90,
    "to": 300
}];

重複しない範囲のセットに変換する必要があります。つまり、次のようになります。

var nonOverlapping = splitRanges(ranges);

/*
nonOverlapping = [{
    "from": 0,
    "to": 49
}, {
    "from": 50,
    "to": 69
}, {
    "from": 70,
    "to": 89
}, {
    "from": 90,
    "to": 100
}, {
    "from": 101,
    "to": 200
}, {
    "from": 201,
    "to": 300
}]
*/

これを行う関数を (JavaScript で) 作成しましたが、もちろん、ご覧のとおり、いわゆる「素朴なアプローチ」を使用しているため、動作が非常に遅くなります。

function splitRanges(ranges) {
    var repeat, length, i, j;
    var rangeA, rangeB, intersection;
    do {
        repeat = false;
        length = ranges.length;
        for (i = 0; i < length; i++) {
            rangeA = ranges[i];
            for (j = i + 1; j < length; j++) {
                rangeB = ranges[j];
                if (isIntersectingRanges(rangeA, rangeB)) {
                    repeat = true;
                    ranges.splice(i, 1);
                    intersection = splitRange(rangeA, rangeB);
                    while (intersection.length) {
                        ranges.push(intersection.shift());
                    }
                }
                if (repeat) break;
            }
            if (repeat) break;
        }
    } while (repeat);
}

誰かがこれを書き直すのを手伝ってくれるので、同じように動作し、素朴なアプローチよりも速くなりますか?

編集：

アルゴリズムは、範囲 ID を追跡できる必要があります + から == までの範囲を正しく処理します。

var ranges = [{
    id: 1,
    from: 0,
    to: 100
}, {
    id: 2,
    from: 30,
    to: 30,
}, {
    id: 3,
    from: 0,
    to: 100
}, {
    id: 4,
    from: 90,
    to: 300
}];

予想される出力は次のとおりです。

[{
    "id": 3,
    "from": 90,
    "to": 100
}, {
    "id": 4,
    "from": 90,
    "to": 100
}, {
    "id": 4,
    "from": 101,
    "to": 300
}, {
    "id": 1,
    "from": 0,
    "to": 29
}, {
    "id": 1,
    "from": 90,
    "to": 100
}, {
    "id": 3,
    "from": 0,
    "to": 29
}, {
    "id": 1,
    "from": 30,
    "to": 30
}, {
    "id": 1,
    "from": 31,
    "to": 89
}, {
    "id": 2,
    "from": 30,
    "to": 30
}, {
    "id": 3,
    "from": 30,
    "to": 30
}, {
    "id": 3,
    "from": 31,
    "to": 89
}]
4

1 に答える 1

1

これにより、指定された入力に対して必要な結果が生成されます。

function splitRanges (intervals) { 'use strict';
  // Create arrays of the from and to values, do not record duplicate values 
  for (var to = [], from = [], n, i = intervals.length; i--;) {
    if (to.indexOf (n = intervals[i].to) < 0)
      to.push (n);
    if (from.indexOf (n = intervals[i].from) < 0)
      from.push (n);
  }

  // Sort both arrays
  to.sort (function (a, b) { return a-b; });
  from.sort (function (a, b) { return a-b; });

  // Create new intervals array
  intervals = [];
  while (to.length)
    intervals.push ({
      from: from.shift (),
      to: from.length == 0 ? (from.push ((n = to.shift ()) + 1), n) :
          from[0] > to[0] ? from[1] - 1 : from[0] - 1
    });

  return intervals;
}

同じ数値が from 値と to 値の両方として表示される場合、「誤った」null 範囲が生成されます。このケースがデータで発生する可能性があるのか​​ 、それとも余分な範囲が問題なのかがわからない

于 2012-05-19T13:36:32.807 に答える