如何在C＃中實現以下邏輯？

Question

我需要爲每個時間表分配頻道。可以爲分配給客戶的信道數量同時發生許多併發事件。即，如果客戶分配了3個頻道，那麼他可以有3個併發事件。如果一個通道被分配給一個事件，那麼同一個通道不能分配給另一個同時發生的事件，但如果時間不同，同一個通道可以分配給另一個事件。

頻道表

ID Name 
1 Name1 
2 Name2 
3 Name3 

事件表

ID EventName StartTime EndTime ChannelID 
1 Event1 11:30AM 12PM 1 
2 Event2 11:30AM 11:40AM 2 
3 Event3 11:40AM 12PM 2 
4 Event4 12PM  12:30PM 1 0r 2 
5 Event5 11:30AM 12:30PM 3 

上面是預期的輸出。

我試圖嵌套foreachloop一個渠道和其他伊芙，但無法實現和複雜性非常高。如何實現這一邏輯？

僞代碼：

for each channel 
{ 
    foreach existing events 
    { 
     if(sametime && same channel) 
      { 
      go for next channel 
      } 
     break; 
    } 
assign current channel to new event 
} 

，當我嘗試創建第三個事件，則此失敗。

Answer 1

可以相當循環是通過向事件分配信道的事件，看看下面的僞代碼：

foreach events 
{ 
    foreach channels 
    { 
     if currentChannel is assigned 
     { 
      foreach assignedEvents 
      { 
       if assignedTime = currentEventTime 
        go to next Channel (continue) 
      } 
      currentEvent.Channel = currentChannel 
      break; 
     } 
     else 
     { 
      currentEvent.Channel = currentChannel 
      break; 
     } 
    } 
} 

Answer 2

你必須產生所有的可能性，並選擇最好的。

這是一個NP完全問題，所以沒有辦法做到這一點既快又正確 - 要麼你通過一些啓發式的方式快速做到這一點，但是你不知道它是否真的做得最好，或者你做得最好它慢，我的意思是慢，但你確定結果是最佳的。

取決於您的數據大小。

編輯： 舉例說明，僅將事件分配給第一個空閒頻道並不總是有效。

我們有3個渠道： CH1，CH2，CH3

我們必須把6個事件：

E1-2 - starts at 1:00 ends at 2:59 
E1-3 - starts at 1:00 ends at 3:59 
E1-3 - starts at 1:00 ends at 3:59 
E4 - starts at 4:00 ends at 4:59 
E4 - starts at 4:00 ends at 4:59 
E3-4 - starts at 3:00 ends at 4:59 

如果你只是分配給你結了第一個自由的地方：

Ch1: E1-2, E4 
Ch2: E1-3, E4 
Ch3: E1-3 
and no place for E3-4 

如果您在不同的順序分配給他們，你會得到

Ch1: E1-2, E3-4 
Ch2: E1-3, E4 
Ch3: E1-3, E4 

而且所有的事件都適合。

所以你必須做某種方式的追溯。

Answer 3

看起來有點類似於我的車輛路徑問題。通道與車輛相同，事件就像是有向無環圖中的節點，當且僅當第一個事件比第二個事件開始時更早結束時，邊緣才從一個事件延伸到另一個事件。

你應該能夠找到公開的算法來解決這個問題。

Answer 4

我固定在代碼中的一些問題。我認爲它現在應該工作

using System; 
    using System.Collections.Generic; 
    using System.Linq; 
    using System.Text; 

namespace ChannelAllocator 
{ 

    class Program 
    { 
     const int _numberOfChannels = 10; 
     static void Main(string[] args) 
     { 
      Dictionary<int, List<TimeSlot>> occupiedChannels = new Dictionary<int, List<TimeSlot>>(); 

      for (int i = 1; i <= _numberOfChannels; i++) 
      { 

       occupiedChannels.Add(i, new List<TimeSlot>()); 
      } 

      /** Example **/ 
      TimeSpan start = DateTime.Now.AddHours(-1.0).TimeOfDay; 
      TimeSpan end = DateTime.Now.TimeOfDay; 
      AssignChannel(occupiedChannels, ref start, ref end);   

     } 

     private static bool AssignChannel(Dictionary<int, List<TimeSlot>> occupiedChannels, ref TimeSpan start, ref TimeSpan end) 
     { 
      List<int> channels = occupiedChannels.Keys.ToList(); 
      if (start >= end) 
       return false; 
      foreach (var item in channels) 
      { 
       List<TimeSlot> slots = occupiedChannels[item]; 
       if (slots.Count == 0) 
       { 
        occupiedChannels[item].Add(new TimeSlot(start, end)); 
        return true; 

       } 
       else 
       { 
        bool available = false ; 
        foreach (var slot in slots) 
        { 
         TimeSpan channelStartTime = slot.StartTime; 
         TimeSpan channelEndTime = slot.EndTime; 

         if (start >= channelStartTime && end <= channelEndTime || 
          start <= channelStartTime && end <= channelEndTime && end >= channelStartTime 
          || end >= channelEndTime && start >= channelStartTime && start <= channelEndTime) 
         { 
          available = false; 
          break;  
         } 
         else { 
          available = true; 
         } 
        } 
        if (available) 
        { 
         occupiedChannels[item].Add(new TimeSlot(start, end)); 
         return true; 
        } 

       } 
      } 
      return false; 
     } 

     private class TimeSlot 
     { 
      public TimeSpan StartTime; 
      public TimeSpan EndTime; 
      public TimeSlot(TimeSpan start, TimeSpan end) 
      { 
       StartTime = start; 
       EndTime = end; 
      } 

     } 

    } 
}