实现在Javascript中检查重叠间隔的算法

Implementing algorithm to check for overlapping intervals in Javascript

本文关键字：算法 重叠 检查 Javascript 实现      更新时间：2023-09-26

尝试在Javascript中实现这个(marcog的答案)重叠间隔算法，但我不能让它工作。

我想检查JSON数据结构中的值，选出代表x1-x2坐标的行开始停止值。我正在一个接一个地添加新行，我想知道添加新行什么时候会导致行重叠。

我得到的错误是，当有明显的重叠时，它总是打印"没有重叠"。

这是我到目前为止的代码:

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

两个错误:

  • 在奇偶校验的情况下，你忘了从你的compcompation函数中去掉return 0。参见JavaScript中的排序:每个比较函数都应该有一个"return 0"声明吗?
  • 您正在尝试从forEach回调到return true。这将只从当前回调返回，而不是从checkOverlappingInterval函数返回。使用every/some，或正常的for循环代替。

我相信这应该能行:

1)按起始值

对json数组进行排序

2)我肯定知道开始总是大于所有以前的开始，所以我唯一要检查的是，如果任何以前的停止大于当前的开始，我正在检查。我用for语句这样做，并将最大停止值保存在一个变量中。所以如果当前起始点大于我设置的最大值，它就会重叠

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);
相关文章：