使用最小位置组织日历事件的算法

Question

我想构建一种算法来组织日历事件以显示位置。

每个事件看起来像这样:

{
  title: 'A Title',
  start: aDate,
  end: anotherDate,
  position: aNumber
}

我想实现类似这样的布局

(A 和 B 的位置为 0，C 和 D 的位置为 1，E 的位置为 2)或任何其他组合，但不要使用不必要的位置。

谁能建议女巫算法可以自动为我的事件分配合适的位置？ (名称引用或伪代码会有很大帮助)

到目前为止，我的想法是在事件对象中跟踪其他重叠事件，然后以某种方式比较它们的位置/重叠(如果有的话)以获得数字，但我不太明白。

Answer 1

鉴于您可以在其中放置事件的多个现有空闲 channel ，其中任何一个都是可以接受的选择，因为所需 channel 的最大总数不会受到影响。鉴于没有空闲车道，只有一个选择:添加一条新车道。

因此，这个问题其实很简单:只需在你能找到的第一个空闲车道上放置一个事件(如果当前没有空闲车道，则创建一个新车道)，并跟踪被占用的车道和时间什么时候他们会被释放。

这种贪婪的方法可能如下所示:

initialize a list of free lanes
for each event e,
   1. check which occupied lanes are free for e.startTime
   2. assign e.lane to a free lane, or add a new free lane if none empty
   3. mark the e.lane as occupied until e.endTime is reached

第 2 步可以坚持使用最少数量的空闲 channel (以产生更紧凑的表示)，或者稍微扩展 channel (这可能具有美学意义，尽管您不知道所需的 channel 总数直到第一次通过之后)。

在任何情况下，该算法只需要一次通过和最少的额外内存(跟踪哪些 channel 被占用到什么时候)。