实现算法来检查Javascript中的重叠区间算法

Question

试图在Javascript中实现this（马克回答）重叠区间算法，但我无法使它工作。

我想查看一个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"); 
    } 
}); 

Answer 1

我认为这应该工作：

1）排序由起始值JSON数组

2）我知道肯定开始总是会比以前所有的开始都要大，所以我必须检查的唯一事情是，如果从前面的停车位大于当前正在检查的位置。我用for做到了这一点，并且我将最大停留在varibale中。因此，如果当前的起始比最大我有了较大，它重叠

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

Answer 2

两个错误：

• 您从您的悲悯功能奇偶校验的情况下忘记return 0。请参阅Sorting in JavaScript: Should every compare function have a "return 0" statement?
• 您正在尝试从forEach回调中拨打return true。这将只从当前回调中返回，而不是从checkOverlappingInterval函数返回。改为使用every/some，或使用正常的for loop。