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 值出现时，就会产生“虚假”空值范围。不知道这种情况是否会发生在您的数据中，或者额外的范围是否有问题

于 2012-05-19T13:36:32.807 回答