Integers range overlap algorithm

Question

I have have a logic problem I cannot seem to wrap my head around. I'm working with sets of discount ranges that a user can change add or remove which I need to validate for overlapping values.

For example, I have an array of min and max integer values [{min: 0, max: 33},{min: 33, max: 66},{min: 66, max: 100}]

I need to determine if any of the given ranges overlap with each other, but the ranges are allowed to overlap by 1 only. The amount of ranges is also variable so there might be any number of sets per array.

eg:
[{min: 0, max: 33},{min: 33, max: 66},{min: 66, max: 100}] or [{min: 5, max: 50},{min: 51, max: 66},{min: 66, max: 100}] should evaluate to true because there is overlapping ranges but only by 1.

[{min: 0, max: 34},{min: 33, max: 66},{min: 66, max: 100}] or [{min: 0, max: 33},{min: 32, max: 66},{min: 66, max: 100}] should evaluate tofalse because the ranges overlap by more than 1.

The following works to find the overlaps but doesn't allow for an overlap by 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

Thank you guys for the assistance. It is much appreciated.

Just an update that uses forEach loops the same way your very helpful for loops do.

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));

Answer 2

You can achieve this by sorting the array based on min value, and comparing the max of current element with min of next element.

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));

Answer 3

You can achieve this by comparing each range with each other.

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
}