整数范围重叠算法

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>

- Riaan Swanepoel

---

你目前尝试了什么？ - Christopher Moore

你可以使用(a,b) => a.max > b.min && b.max > a.min来确定两个元素是否重叠。 - Thomas

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
}

- Manuel Otto

---

谢谢@Manuel Otto，你的代码片段完美地解决了我的问题。它允许重叠一个位置，这正是我卡住的地方。感谢所有提供帮助的人，非常感激。 - Riaan Swanepoel

Answer 2

你可以通过按最小值对数组进行排序，并将当前元素的最大值与下一个元素的最小值进行比较来实现此目标。

var kf =  [{min: 0, max: 34},{min: 33, max: 66},{min: 66, max: 100}];
var kt =  [{min: 0, max: 33},{min: 33, max: 66},{min: 66, max: 100}];



kf.sort(function(a, b) {
    return parseFloat(a.min) - parseFloat(b.min);
});

kt.sort(function(a, b) {
    return parseFloat(a.min) - parseFloat(b.min);
});

var isvalid = function(k){
    for (var i=0, l=k.length; i<l-1; i++) 
    { 
 if(k[i].max - k[i+1].min > 0)
 return false;
} 
return true;
}

console.log(isvalid(kf));

console.log(isvalid(kt));

- anvita surapaneni

---

谢谢@anvita surapaneni，你的片段完美地发挥了作用。它允许重叠一个，这正是我卡住的地方。感谢所有提供帮助的人，非常感激。 - Riaan Swanepoel

Answer 3

感谢您们的帮助，非常感激。

只是一个更新，使用forEach循环方式与您非常有帮助的for循环相同。

let rangeArr =  [{min: 0, max: 33},{min: 33, max: 66},{min: 66, max: 100}];

let checkRangeOverlap = (ranges) => {
 let err = false;
    ranges.forEach(function(a,ia){

        ranges.forEach(function(b,ib){
            if(a !== b){
                if(a.min < b.max && a.max > b.min){
      err = true;
    }
                   
            }
        });
        
    });
 return err;
}

console.log(checkRangeOverlap(rangeArr), JSON.stringify(rangeArr));

rangeArr =  [{min: 0, max: 33},{min: 33, max: 67},{min: 66, max: 100}];

console.log(checkRangeOverlap(rangeArr), JSON.stringify(rangeArr));

- Riaan Swanepoel