Как добиться приведенной ниже логики в 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 один для канала, а другой для evets, но не смог достичь и сложностидействительно высоко.Как добиться этой логики?

Псевдокод:

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

Я исправил некоторые проблемы в коде.Я думаю, что это должно работать сейчас

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

        }

    }
}

Answer 3

Похоже, для меня проблема с маршрутизацией транспортных средств. Каналы такие же, как у транспортных средств, а события похожи на узлы в ориентированном ациклическом графе с ребрами, ведущими от одного события к другому, если и только если первое событие заканчивается раньше, чем начинается второе.

Вы должны быть в состоянии найти общедоступные алгоритмы для решения этой проблемы.

Answer 4

Вы должны сгенерировать все возможности и выбрать лучший.

Это NP-полная проблема, поэтому нет способа сделать это и быстро, и правильно - либо вы делаете это быстро с помощью некоторой эвристики, но тогда вы не знаете, действительно ли это было лучше, или вы делаете это медленно, и я имею в виду медленно, но вы уверены, что результат является оптимальным.

Зависит от размера ваших данных.

EDIT: Пример, демонстрирующий, что просто присвоение событий первому свободному каналу не всегда будет работать.

У нас есть 3 канала: Ч1, Ч2, Ч3

Мы должны разместить 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

И все события подойдут.

Так что вы должны каким-то образом выполнить возврат.