在 Google 日历样式事件列表中检测范围重叠

Question

我需要帮助修复我现有的代码以完成我正在尝试做的事情。

使用以下示例数据：

var SAMPLE_DATA = [{start: 30, end: 150}, {start: 540, end: 600}, {start: 560, end: 620}, {start: 610, end: 670}];

我需要执行以下操作：

遍历每个样本对象
确定当前对象范围 (obj.start:obj.end) 是否与任何其他对象范围重叠。
将该对象的重叠总数记录到 totalSlots 属性
确定对象的"index"（用于从左到右的定位）

我想要完成的模型：

正如您在模型中看到的，slotIndex 用于确定显示的从左到右的顺序。 totalSlots 是它与 space 共享的对象数量（1 表示它是唯一的对象）。 100 / totalSlots 告诉我正方形可以有多宽（即 totalSlots=2，表示它是 100 / 2，或容器宽度的 50%）。

我的代码的当前输出

Obj[0] slotIndex=0, totalSlots=0
Obj[1] slotIndex=1, totalSlots=1
Obj[2] slotIndex=1, totalSlots=2
Obj[3] slotIndex=0, totalSlots=1

expected/desired 我的代码输出：

Obj[0] slotIndex=0, totalSlots=0
Obj[1] slotIndex=0, totalSlots=1
Obj[2] slotIndex=1, totalSlots=2
Obj[3] slotIndex=0, totalSlots=1

代码：

detectSlots: function(oldEventArr) {
  oldEventArr.sort(this.eventSorter);
  var newEventArr = [],
    n = oldEventArr.length;

  for (var i = 0; i < n; i++) {
    var currObj = oldEventArr[i];
    if ('undefined' == typeof currObj.totalSlots) {
      currObj.slotIndex = 0;
      currObj.totalSlots = 0;
    }
    for (var x = 0; x < n; x++) {
      if (i == x) { 
        continue;
      }
      var nextObj = oldEventArr[x];
      if (currObj.start <= nextObj.end && nextObj.start <= currObj.end) {
        currObj.totalSlots++;
        nextObj.slotIndex++;

      }
    }
    newEventArr.push(currObj);
  }
  return newEventArr;
}

请帮我找出我的代码出了什么问题。我大约 90% 确定问题出在我 assigning/incrementing 值的 if(currObj.start <= nextObj.end && nextObj.start <= currObj.end) 语句中，但我可以对此多加注意。

Answer 1

像这样

var not_overlap = (currObj.end <= nextObj.start || nextObj.end <= currObj.start);
if (!not_overlap) { ...

或

var overlap = (currObj.end > nextObj.start && nextObj.end < currObj.start);
if (overlap) { ...

Answer 2

slotIndex值可以通过图形着色算法计算得到。请注意，蛮力算法在时间上是指数级的，并且仅适用于一小组重叠插槽的可行解决方案。其他算法是启发式算法，您不能保证尽可能少的插槽。

这是针对您的问题的启发式示例：

...
// init
  var newEventArr = [], n = oldEventArr.length;

  for (var i = 0; i < n; i+=1) {
    var currObj = oldEventArr[i];
    newEventArr.push({"start":currObj.start,"end":currObj.end,"slotIndex":undefined,"totalSlots":0});
  }

  var link = {};

  // create link lists and totals
  for (var i = 0; i < n; i+=1) {
    var currObj = newEventArr[i];
    if (!link.hasOwnProperty(""+i))
      link[""+i] = {};

    for (var j = i+1; j < n; j+=1) {
      var nextObj = newEventArr[j];
      var not_overlap = (currObj.end <= nextObj.start || nextObj.end <= currObj.start);
      if (!not_overlap) {        
        currObj.totalSlots+=1;
        nextObj.totalSlots+=1;

        link[""+i][""+j] = 1;
        if (!link.hasOwnProperty(""+j))
          link[""+j] = {};
        link[""+j][""+i] = 1;
      }
    }
  }

  var arrities = [];
  for (var i = 0; i < n; i+=1) {
    arrities.push( {"arrity":newEventArr[i].totalSlots, "indx":i} );
  }

  // sort by arrities [a better solution is using a priority queue]
  for (var i = 0; i < n-1; i+=1) {
    var current_arrity = -1, indx = -1;
    for (var j = i; j < n; j+=1) {
      if (arrities[j].arrity > current_arrity) {
        indx = j;
        current_arrity = arrities[j].arrity;
      }
    }
    var temp = arrities[i];
    arrities[i] = arrities[indx];
    arrities[indx] = temp;
  }

  for (var i = 0; i < n; i+=1) {
    var nodeIndex = arrities[i].indx;
    // init used colors
    var colors = [];
    for (var j = 0; j < n; j+=1) {
      colors.push(0);
    }
    //find used colors on links
    for (var k in link[""+nodeIndex]) {
      var color = newEventArr[k].slotIndex;
      if (color || color === 0)
        colors[color] += 1;
    }
    //find the first unused color
    for (var j = 0; j < n; j+=1) {
      if (colors[j] <= 0) {
        // color the node
        newEventArr[nodeIndex].slotIndex = j;
        break;
      }
    }
  }
  return newEventArr;
...

在 Google 日历样式事件列表中检测范围重叠

detecting range overlaps in Google Calendar-Style event list

javascript

arrays

algorithm

for-loop

range