javascript - 整数范围重叠算法

Question

我有一个逻辑问题，我似乎无法解决问题。我正在处理用户可以更改添加或删除的折扣范围集，我需要验证重叠值。

例如，我有一个最小和最大整数值数组 [{min: 0, max: 33},{min: 33, max: 66},{min: 66, max: 100}]

我需要确定给定范围是否相互重叠，但这些范围只允许重叠 1。范围的数量也是可变的，因此每个数组可能有任意数量的集合。

例如:
[{min: 0, max: 33},{min: 33, max: 66},{min: 66, max: 100}]或 [{min: 5, max: 50},{min: 51, max: 66},{min: 66, max: 100}] 应计算为 true，因为存在重叠范围但仅相差 1。

[{min: 0, max: 34},{min: 33, max: 66},{min: 66, max: 100}]或者[{min: 0, max: 33},{min: 32, max: 66},{min: 66, max: 100}] 应该评估为false 因为范围重叠超过 1。

下面的工作是找到重叠，但不允许重叠 1。

var overlappedRanges = [{
  min: 0,
  max: 33
}, {
  min: 33,
  max: 66
}, {
  min: 66,
  max: 100
}];
var nonOverlappedRanges = [{
  min: 0,
  max: 32
}, {
  min: 33,
  max: 66
}, {
  min: 67,
  max: 100
}];

var checkForOverlap = function(arr) {
  var err = false;
  arr.forEach(function(e, i) {
    arr.forEach(function(ee, ii) {
      if (ee !== e) {
        if (e.min >= ee.min && e.min <= ee.max) {
          err = true;
        }

        if (e.max >= ee.min && e.max <= ee.max) {
          err = true;
        }
      }
    });
  });

  if (err) {
    return 'Overlap Found in ' + JSON.stringify(arr);
  } else {
    return 'NO Overlap Found in ' + JSON.stringify(arr);
  }
}

$('#overlapped').text(checkForOverlap(overlappedRanges));
$('#notOverlapped').text(checkForOverlap(nonOverlappedRanges))

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<span id="overlapped" style="color: red;"></span>
<br>
<span id="notOverlapped" style="color: green;"></span>

Answer 1

您可以通过相互比较每个范围来实现这一点。

function checkRangeOverlap(ranges){
    var n = ranges.length // store length for performance gains

    for(var i=0;i<n;i++){
        for(var u=0;u<n;u++){
            if(i==u) // skip if comparing the same range
                continue

            var rangeA = ranges[i]
            var rangeB = ranges[u]

            if(rangeA.min < rangeB.max && rangeA.max > rangeB.min) // if the ranges intersect
                return false
        }
    }

    return true // no intersections found
}