Implementing algorithm to check for overlapping intervals in Javascript

Question

Trying to implement this (marcog's answer) overlapping intervals algorithm in Javascript but I can't get it working.

I want to go over the values in a JSON data structure picking out start stop values representing x1-x2 coordinates for lines. Im adding new lines one after the other and I want to know when adding a new line would result in overlapping lines.

The error I'm getting is that it always prints "no overlaps" when there clearly are overlaps.

This is the code I have so far:

var
data = [],
json = [
  { 
    "start" : 100,
    "stop" : 800
  },
  { 
    "start" : 900,
    "stop" : 1200
  },
  { 
    "start" : 200,
    "stop" : 600
    }
],
    sortInterval, checkOverlappingInterval;

sortInterval = function (value) {
  //Sorts a list with lower numbers first and end point come before 
  //starting points on ties
  value.sort(function (a,b){
    var aSplit = a.split("_"),
        bSplit = b.split("_");
    if (aSplit[0] * 1 > bSplit[0] * 1){
      return 1;
    }
    if (aSplit[0] * 1 < bSplit[0] * 1) {
      return -1;
    } else {
      if (aSplit[1] > bSplit[1]) {
        return 1;
      } else {
        return -1;
      }
    }
  });
};

checkOverlappingInterval = function(value){
  //Return true if there are overlapps
  var inInterval = false;
  value.forEach(function(v) {
    if (v.charAt(v.length-1) === "S"){
      if(inInterval){
        return true;
      }
      else {
        inInterval = true;
      }
    }
    else {
      inInterval = false;
    }

  });
  //return true;

  return false;
};

json.forEach(function (value) {
  //Push the new values to interval array and sort the array
  data.push(value.start + "_S");
  data.push(value.stop + "_E");
  sortInterval(data);
  //Check to see if the new line caused an overlapping line
  //If it did increase y and clear out data
  if (checkOverlappingInterval(data)){
    console.log("overlaps");
  } 
  //If it did not print line
  else {
    console.log("no overlaps");
  }
});

Which of the algorithms? The answers seem to propose multiple different ones. — Bergi, Jul 08 '14 at 16:14

juvian · Answer 1 · 2014-07-08T16:35:59.023

I believe this should work:

1) Sort the json array by start value

2) I know for sure that the start will always be greater than all the previous starts, so the only thing I have to check is if the stop from any previous is greater than the current start I'm checking. I do that with the for and I keep the max stop in a varibale. So if the current start is greater than the max I had, it overlaps

json = [
  { 
    "start" : 100,
    "stop" : 800
  },
  { 
    "start" : 900,
    "stop" : 1200
  },
  { 
    "start" : 200,
    "stop" : 600
    },
    {"start":700, "stop":800}
];

function checkOverlaps(arr){
    arr=arr.slice(0);
    arr.sort(function(a,b){return a.start-b.start});
    var max=0;
    for(var i=1;i<arr.length;i++){
        max=arr[i-1].stop > max ? arr[i-1].stop : max;
        if(arr[i].start < max){
            console.log(arr[i],"overlaps");
        }
    }
}
checkOverlaps(json);

score 0 · Answer 2 · edited May 23 '17 at 10:32

0

Two mistakes:

You forgot to return 0 from your compasion function in case of a parity. See Sorting in JavaScript: Should every compare function have a "return 0" statement?
You are trying to return true from the forEach callback. That will only return from the current callback, not from the checkOverlappingInterval function. Use every/some, or a normal for loop instead.

edited May 23 '17 at 10:32

Community

1
1

answered Jul 08 '14 at 16:29

Bergi

630,263
148
957
1,375

Implementing algorithm to check for overlapping intervals in Javascript

2 Answers2