How to achieve the below logic in C#?

I need to assign channel for each schedule. There can be as many concurrent events as number of channels allocated for the customer. I.e if the customer is allocated 3 channels then he can have 3 concurrent events. If a channel was allocated to a event then the same channel cannot to allocated to another event that falls under same time but the same channel can be allocate to another event if the time differs.

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

The above is the expected output.

I tried nested foreachloop one for channel and other for evets, but was not able to achieve and the complexity is really high. How to achieve this logic?

Pseud开发者_运维知识库o Code:

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

This fail when I try to create 3rd event.

---

You can rather loop through events for assigning channels to event, check out below pseudo code:

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

---

Looks somewhat similar to Vehicle Routing Problem to me. Channels are the same as vehicles and events are like nodes in a directed acyclic graph with edges leading from one event to another if and only if the first event finishes earlier than the second one starts.

You should be able to find publicly available algorithms for solving this problem.

---

You have to generate all possibilities, and choose the best.

It is NP-complete problem, so there's no way to do it both fast and correct - either you do it fast by some heuristic, but then you don't know if it really did the best job, or you do it slow, and i mean slow, but you are sure the result is optimal.

Depends on the size of your data.

EDIT: Example to demonstrate, that just assigning events to the first free channel won't always work.

We have 3 channels: Ch1, Ch2, Ch3

We have to place 6 events:

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

If you just assign to the first free place you'll end up with:

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

If you assigned them in different order, you'll get

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

And all the events would fit.

So you have to do backtracing somehow.

---

I fixed some problems in the code. I think it should work now

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

        }

    }
}