將重疊序列拼合成連續集

Question

對於Ruby on Rails規劃應用程序，我遇到了一個算法/組合問題，我無法有效解決問題。

在我的應用程序有2種類型的記錄：

• 有效性的（當有人免費提供，在待機或明確不可用（生病，休假））
• 計劃記錄（當有人實際預定在）。

這兩種類型的記錄都由開始和結束時間定義，並且可用性具有附加類型（可用，備用，不可用）。

現在我想獲得的平面列表非重疊時期，顯示我，當有人有計劃記錄第一，但還具有可用性

舉個例子：

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

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

期望的結果是3個非重疊期：

• 3-6：可用
• 6-15：計劃
• 15-18：待機

另一實例，在一個狀況需要被拆分：

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

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

期望的結果是3個非重疊時期：

• 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小時以上的值。

考慮上面的第二個例子。

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和​​這些值，與註釋掉最後一行，我獲得

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