ruby - 我如何安排到泳道

Question

我正在尝试将 10000 个事件安排到不同的 channel 中。每个事件都有开始和结束日期。任何事件都不能在一条泳道中重叠。

    ======================================================================
Lane 1   [Event1]      [Event4       ]  [Event7   ]
    ======================================================================
    ======================================================================
Lane 2         [Event2]            [Event 5]      [Event 8]
    ======================================================================
    ======================================================================
Lane 3     [Event3        ]       [Event6]      
    ======================================================================
    ========time along x axis        >>>>>>>>>>>>>>>>>>>>>>>>>>

所以我的问题是有效地为事件确定合适的 channel 。我从数据库中获取按开始时间排序的事件。我采用的第一种方法是为每条车道设置一个 last_end_time。对于每个新事件，我都会检查每条车道，如果事件的开始时间早于车道的最后结束时间，我会向下移动并检查下一条车道。如果我找不到适合它的车道，我会创建一个新车道。

class LaneManager
  def initialize
    @lanes = []
  end

  # Find the free lane given start and end of an event
  def nextFreeLane start_date, end_date
    @lanes.each_with_index do |lane, index|
      if start_date > lane.last_date
        lane.last_date = end_date
        return index
      end
    end
    lane = Lane.new
    lane.last_date = end_date
    @lanes << lane
    @lanes.length - 1
  end
end

class Lane
  attr_accessor :last_date
end

然而，这会遇到另一个问题。如果我有 5000 个具有相同开始和结束的事件，然后要为 5001 事件找到一个插槽，我最终会检查之前的 5000 个 channel ，依此类推。性能只会下降。

关于如何有效地存储、查询事件有什么建议吗？我需要在网页上呈现它们。我有水平和垂直滚动来平移事件。对于垂直滚动，我告诉我的服务器——这些是我需要的 channel (比如 channel 5 到 channel 10)。对于水平滚动，我只是使用新的时间窗口和所需的车道进行新查询，这基本上是一组新的事件。

我的问题是垂直滚动，我需要有效地将所有事件放入正确的 channel 中。如果我能有效地做到这一点，那么我就可以查询我的服务器以获取 channel 中的事件，比如 26-30。将不胜感激任何建议。

Answer 1

首先，将开始时间和结束时间合为一组，并按时间排序。对于每个结尾，找到最近的下一个开头，并链接到它。完成后，解开线索:取第一个开始并将其连同与之相关的整个事件链一起从束中取出(请记住，每一端都与最近的开始相关联)。重复该过程，直到束中没有事件开始(因此没有事件)。