實現算法來檢查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。