将重叠序列平坦化成一个连续集

Question

对于Rails规划应用程序，我遇到了一个算法/组合问题，很难有效地解决。

在我的应用程序中，我有两种类型的记录：

• 可利用性(当某人可以免费提供、随时待命或明显无法使用(病假、休假))
• 计划记录(实际安排在什么时候)。

这两种类型的记录都是由开始时间和结束时间定义的，并且可用性还有一个额外的类型(可用、备用、不可用)。

现在，我想得到一个non-overlapping句点的简单列表，它可以显示某人什么时候有计划记录，但另外还有可用的

举一个例子：

Time:  0-----------6-----------12-----------18-----------24
Avail:     |-----available-----||--standby--|
Plans:             |------------------|

Result:    |------||------------------||----|

期望的结果是三个不重叠的时期：

• 3-6:可得
• 6-15:计划
• 15-18:待命

另一个例子是，需要分割可用性：

Time:  0-----------6-----------12-----------18-----------24
Avail:     |-----available-----||--standby--|
Plans:             |-----|

Result:    |------||-----||----||-----------|

期望的结果是三个不重叠的时期：

• 3-6:可得
• 6-9:计划
• 9-12:可得
• 12-18:待命

数组中已经有了所有(重叠的)句点。有效率地实现我想要的目标的最好方法是什么？

Answer 1

我假设我们有“计划”、“可用”和“覆盖”的小时范围，其中“覆盖率”是“可用”范围之前的“可用”范围，后面是“待命”范围。此外，“覆盖”包含“计划”，其“备用”范围的任一或两个都可能是零持续时间。

码

def categories(avail, plan)
  adj_avail = adj_avail(avail)
  adj_plan  = adj_plan(avail, plan)
  arr = []
  finish = [adj_avail[:available][:start], adj_plan[:start]].min
  add_block(arr, :standby, adj_avail[:coverage][:start], finish)
  start = finish
  finish = [adj_avail[:available][:finish], adj_plan[:start]].min
  add_block(arr, :available, start, finish)
  start = finish
  add_block(arr, :standby, finish, adj_plan[:start])
  arr << [:plan, adj_plan]
  finish = [adj_plan[:finish], adj_avail[:available][:finish]].max
  add_block(arr, :available, adj_plan[:finish], finish)
  add_block(arr, :standby, finish, adj_avail[:coverage][:finish])
  restore_times(arr)
end

​

def adj_avail(avail)
  avail.each_with_object({}) do |(k,g),h|
    start, finish = g[:start], g[:finish]
    h[k] = case k
    when :coverage
      { start:  start, finish: finish + (finish < start ? 24 : 0) }
    else # when :available
      { start:  start + (start < h[:coverage][:start] ? 24 : 0), 
        finish: finish + (finish < start ? 24 : 0) }
    end
  end
end

def adj_plan(avail, plan)
  { start:  plan[:start]  + (plan[:start]  < avail[:coverage][:start] ? 24 : 0),
    finish: plan[:finish] + (plan[:finish] < plan[:start] ? 24 : 0) }
end

def add_block(arr, value, curr_epoch, nxt_epoch)  
  arr << [value, { start: curr_epoch, finish: nxt_epoch }] if nxt_epoch > curr_epoch
end

def restore_times(arr)
  arr.map! do |k,g|
    start, finish = g.values_at(:start, :finish)
    start  -= 24 if start  > 24
    finish -= 24 if finish > 24
    [k, { start: start, finish: finish }]
  end
end

示例

avail = { coverage:  { start: 3, finish: 18 },
          available: { start: 3, finish: 12 } }
plan  = { start: 6, finish: 15 }
categories(avail, plan)
  #=> [[:available, {:start=>3, :finish=>6}  ],
  #    [:plan,      {:start=>6, :finish=>15} ],
  #    [:standby,   {:start=>15, :finish=>18}]] 

avail = { coverage:  { start: 22, finish: 11 },
          available: { start: 23, finish: 10 } }
plan  = { start: 24, finish: 9 }
categories(avail, plan)
  #=> [[:standby,   {:start=>22, :finish=>23}],
  #    [:available, {:start=>23, :finish=>24}],
  #    [:plan,      {:start=>24, :finish=>9 }],
  #    [:available, {:start=>9,  :finish=>10}],
  #    [:standby,   {:start=>10, :finish=>11}]] 

avail = { coverage:  { start: 1, finish: 13 },
          available: { start: 2, finish: 3 } }
plan  = { start: 4, finish: 12 }
categories(avail, plan)
  #=> [[:standby,   {:start=>1,  :finish=>2 }],
  #    [:available, {:start=>2,  :finish=>3 }],
  #    [:standby,   {:start=>3,  :finish=>4 }],
  #    [:plan,      {:start=>4,  :finish=>12}],
  #    [:standby,   {:start=>12, :finish=>13}]]

解释

这里最复杂的是“覆盖”的结束时间小于开始时间，这意味着“覆盖”范围包含午夜。当发生这种情况时，“可用”和“计划”范围也可能包含午夜。我已经处理了这个问题，在计算范围之前，在午夜后的24小时到24小时之后，然后从计算范围后超过24小时的所有小时值中减去24小时。

考虑上面的第二个例子。

avail = { coverage:  { start: 22, finish: 11 },
          available: { start: 23, finish: 10 } }
adj_avail(avail)
  #=>   {:coverage=> {:start=>22, :finish=>35},
  #      :available=>{:start=>23, :finish=>34}} 

plan  = { start: 24, finish: 9 }
adj_plan(avail, plan)    
  #=> {:start=>24, :finish=>33}

如果我对categories和avail和plan的值执行这些值，并将最后一行注释掉，我将获得

a = categories(avail, plan)    
  #=> [[:standby,   {:start=>22, :finish=>23}],
  #    [:available, {:start=>23, :finish=>24}],
  #    [:plan,      {:start=>24, :finish=>33}],
  #    [:available, {:start=>33, :finish=>34}],
  #    [:standby,   {:start=>34, :finish=>35}]]

和

restore_times(a)
  #=> the return value shown above