下面的逻辑如何用C#实现？

Question

我需要为每个时间表分配频道。并发事件的数量可以与为客户分配的通道数量一样多。即，如果为客户分配了 3 个通道，那么他可以有 3 个并发事件。如果将一个通道分配给一个事件，则同一通道不能分配给同一时间的另一个事件，但如果时间不同，则可以将同一通道分配给另一个事件。

Channel Table

ID Name
1  Name1
2  Name2
3  Name3

Event Table

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

对我来说，看起来有点类似于车辆路径问题。通道与车辆相同，事件就像有向无环图中的节点，当且仅当第一个事件早于第二个事件开始时，边从一个事件通向另一个事件。

您应该能够找到公开可用的算法来解决此问题。

Answer 3

你必须产生所有的可能性，并选择最好的。

这是 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 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;
            }

        }

    }
}