Avatar billede lasserasch Juniormester
23. oktober 2017 - 16:49 Der er 6 kommentarer og
1 løsning

Find bedste kombination af Timeslots

Hejsa.

Har brug for lidt nye ideér til at løse dette problem.
Håber en har lidt input.

Jeg har en custom klasse kaldet et 'TimeSlot'.
Et timeslot repræsenterer en åben kalender tid hos en ressource.
Den har bl.a. følgende properties :

Id
Name
StartTime
EndTime


Jeg har så f.eks. 3 kalendere. En for hver ressource.

Dette er repræsenteret via 3 lister.

Altså :

var ListA = new List<TimeSlot>();
var ListB = new List<TimeSlot>();
var ListC = new List<TimeSlot>();


Hver af disse kalendere har nogle ledige timeslots.

Ex.

ListA.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-10), EndTime = DateTime.Now.AddHours(-9), Id = Guid.NewGuid() });
ListA.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-8), EndTime = DateTime.Now.AddHours(-7), Id = Guid.NewGuid() });

ListB.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-7), EndTime = DateTime.Now.AddHours(-6), Id = Guid.NewGuid() });
ListB.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-6), EndTime = DateTime.Now.AddHours(-4), Id = Guid.NewGuid() });
ListB.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-3), EndTime = DateTime.Now.AddHours(-2), Id = Guid.NewGuid() });

ListC.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-7), EndTime = DateTime.Now.AddHours(-6), Id = Guid.NewGuid() });
ListC.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-1), EndTime = DateTime.Now, Id = Guid.NewGuid() });


Jeg har brug for at kunne finde frem til den bedste kombination mellem de 3 kalendere, hvor tiderne ligger så tæt på hinanden som muligt, uden at overlappe.

Det er lige meget i hvilken rækkefølge, men der må være en smart måde hvorpå man kan finde den kombination, som giver den mindste ventetid mellem timeslots.

Ex. hvis en bruger tager til lægehuset og hver kalender her repræsenter en type læge. F.eks. En "Alm. læge", en "Ørelæge" og en "Øjenlæge".
Jeg har brug for at få retuneret 3 Timeslots i en liste, som er den kombination der skaber mindst ventetid for patienten mellem konsultationer.

Håber det giver mening.

Nogen ide til hvordan man gør det nemmeste?

I ovenstående eksempel ville den bedste kombi være :

Liste A - Entry nr. 2. +
Liste B - Entry nr. 1 +
Liste C - Entry nr. 2


Mvh.
Lasse
Avatar billede lasserasch Juniormester
23. oktober 2017 - 16:52 #1
Og det er så faktisk ikke korrekt. Den mest optimale kombination af ovenstående timeslots ville være :

Liste A - Entry nr. 2. +
Liste C - Entry nr. 1 +
Liste B - Entry nr. 2
Avatar billede arne_v Ekspert
23. oktober 2017 - 20:30 #2
Mit forslag:


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

namespace E
{
    public class TimeSlot
    {
        public DateTime StartTime { get; set; }
        public DateTime EndTime { get; set; }
        public Guid Id { get; set; }
    }
    public class Booker
    {
        private static int Wait(TimeSlot[] a)
        {
            TimeSlot[] a2 = a.OrderBy(elm => elm.StartTime).ToArray();
            int res = 0;
            for(int i = 0; i < a2.Length - 1; i++)
            {
                if(a2[i].EndTime > a2[i + 1].StartTime)
                {
                    return int.MaxValue;
                }
                else
                {
                    res += (int)(a2[i + 1].StartTime - a2[i].EndTime).TotalMinutes;
                }
            }
            return res;
        }
        private static int Wait(List<TimeSlot>[] lists, int[] picks)
        {
            TimeSlot[] a = new TimeSlot[lists.Length];
            for(int i = 0; i < a.Length; i++)
            {
                a[i] = lists[i][picks[i]];
            }
            return Wait(a);
        }
        private static void FindOptimal(List<TimeSlot>[] lists, int ix, int[] work, int[] res)
        {
            for(int i = 0; i < lists[ix].Count; i++)
            {
                work[ix] = i;
                if(ix + 1 < work.Length)
                {
                    FindOptimal(lists, ix + 1, work, res);
                }
                else
                {
                    int lowscore = Wait(lists, res);
                    int currscore = Wait(lists, work);
                    if(currscore < lowscore)
                    {
                        Array.Copy(work, res, res.Length);
                    }
                }
            }
        }
        public static int[] FindOptimal(params List<TimeSlot>[] lists)
        {
            int[] res = new int[lists.Length];
            int[] work = new int[lists.Length];
            FindOptimal(lists, 0, work, res);
            return res;
        }
    }
    public class Program
    {
        public static void Main(string[] args)
        {
            List<TimeSlot> ListA = new List<TimeSlot>();
            List<TimeSlot> ListB = new List<TimeSlot>();
            List<TimeSlot> ListC = new List<TimeSlot>();
            ListA.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-10), EndTime = DateTime.Now.AddHours(-9), Id = Guid.NewGuid() });
            ListA.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-8), EndTime = DateTime.Now.AddHours(-7), Id = Guid.NewGuid() });
            ListB.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-7), EndTime = DateTime.Now.AddHours(-6), Id = Guid.NewGuid() });
            ListB.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-6), EndTime = DateTime.Now.AddHours(-4), Id = Guid.NewGuid() });
            ListB.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-3), EndTime = DateTime.Now.AddHours(-2), Id = Guid.NewGuid() });
            ListC.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-7), EndTime = DateTime.Now.AddHours(-6), Id = Guid.NewGuid() });
            ListC.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-1), EndTime = DateTime.Now, Id = Guid.NewGuid() });
            int[] res = Booker.FindOptimal(ListA, ListB, ListC);
            Console.WriteLine("A: {0} B: {1} C: {2}", res[0], res[1], res[2]);
            Console.ReadKey();
        }
    }
}
Avatar billede arne_v Ekspert
23. oktober 2017 - 21:55 #3
Koden kan nok forbedres lidt her og der. Bl.a. maa lowscore kunne genbruges fremfor bergens hver gang. Og score funktionen burde vel vaere et argument. Og maaske kunne man goere Booker til en Planner<TimeSlot>. O.s.v..
Avatar billede arne_v Ekspert
24. oktober 2017 - 04:54 #4
Forbedret forslag:


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

namespace E
{
    public class TimeSlot
    {
        public DateTime StartTime { get; set; }
        public DateTime EndTime { get; set; }
        public Guid Id { get; set; }
    }
    public class Planner<T>
    {
        private static int highscore = int.MinValue;
        private static Tuple<bool, int> Score(Func<T[], Tuple<bool,int>> f, List<T>[] lists, int[] picks)
        {
            T[] a = new T[lists.Length];
            for(int i = 0; i < a.Length; i++)
            {
                a[i] = lists[i][picks[i]];
            }
            return f(a);
        }
        private static void FindLargest(Func<T[], Tuple<bool,int>> f, List<T>[] lists, int ix, int[] work, int[] res)
        {
            for(int i = 0; i < lists[ix].Count; i++)
            {
                work[ix] = i;
                if(ix + 1 < work.Length)
                {
                    FindLargest(f, lists, ix + 1, work, res);
                }
                else
                {
                    Tuple<bool, int> curr = Score(f, lists, work);
                    if(curr.Item1 && curr.Item2 > highscore)
                    {
                        Array.Copy(work, res, res.Length);
                        highscore = curr.Item2;
                    }
                }
            }
        }
        public static int[] FindLargest(Func<T[], Tuple<bool,int>> f, params List<T>[] lists)
        {
            int[] res = new int[lists.Length];
            int[] work = new int[lists.Length];
            FindLargest(f, lists, 0, work, res);
            return res;
        }
        public static int[] FindSmallest(Func<T[], Tuple<bool,int>> f, params List<T>[] lists)
        {
            return FindLargest((a) => { Tuple<bool, int> temp = f(a); return Tuple.Create(temp.Item1, - temp.Item2); }, lists);
        }
    }
    public class Program
    {
        private static Tuple<bool,int> WaitTime(TimeSlot[] a)
        {
            TimeSlot[] a2 = a.OrderBy(elm => elm.StartTime).ToArray();
            int res = 0;
            for(int i = 0; i < a2.Length - 1; i++)
            {
                if(a2[i].EndTime > a2[i + 1].StartTime)
                {
                    return Tuple.Create(false, 0);
                }
                else
                {
                    res += (int)(a2[i + 1].StartTime - a2[i].EndTime).TotalMinutes;
                }
            }
            return Tuple.Create(true, res);
        }
        public static void Main(string[] args)
        {
            List<TimeSlot> ListA = new List<TimeSlot>();
            List<TimeSlot> ListB = new List<TimeSlot>();
            List<TimeSlot> ListC = new List<TimeSlot>();
            ListA.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-10), EndTime = DateTime.Now.AddHours(-9), Id = Guid.NewGuid() });
            ListA.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-8), EndTime = DateTime.Now.AddHours(-7), Id = Guid.NewGuid() });
            ListB.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-7), EndTime = DateTime.Now.AddHours(-6), Id = Guid.NewGuid() });
            ListB.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-6), EndTime = DateTime.Now.AddHours(-4), Id = Guid.NewGuid() });
            ListB.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-3), EndTime = DateTime.Now.AddHours(-2), Id = Guid.NewGuid() });
            ListC.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-7), EndTime = DateTime.Now.AddHours(-6), Id = Guid.NewGuid() });
            ListC.Add(new TimeSlot() { StartTime = DateTime.Now.AddHours(-1), EndTime = DateTime.Now, Id = Guid.NewGuid() });
            int[] res = Planner<TimeSlot>.FindSmallest(WaitTime, ListA, ListB, ListC);
            Console.WriteLine("A: {0} B: {1} C: {2}", res[0], res[1], res[2]);
            Console.ReadKey();
        }
    }
}
Avatar billede lasserasch Juniormester
24. oktober 2017 - 10:09 #5
Super Arne. Mange tak for input. Det vil jeg forsøge at implementere her i dag. :-) :-)
Avatar billede lasserasch Juniormester
24. oktober 2017 - 13:44 #6
Det spiller. Jeg har dog rettet metoderne, så de ikke er statiske.

Hvis man eksekverer den consol applikation du har lavet, med denne lille tilføjelse til, så vil man se at resultatet er 0,0,0 i andet forsøg.

Jeg er ikke helt sikker på hvorfor, men retter man de statiske metoder til, så virker det fint. Tænker der er en værdi som ikke bliver nulstillet mellem kaldene.

Mange tak for hjælpen Arne.


int[] res = Planner<TimeSlot>.FindSmallest(WaitTime, ListA, ListB, ListC);
            Console.WriteLine("A: {0} B: {1} C: {2}", res[0], res[1], res[2]);
            Console.ReadKey();
            res = Planner<TimeSlot>.FindSmallest(WaitTime, ListA, ListB, ListC);
            Console.WriteLine("A: {0} B: {1} C: {2}", res[0], res[1], res[2]);
            Console.ReadKey();

Avatar billede arne_v Ekspert
24. oktober 2017 - 17:29 #7
private static int highscore = int.MinValue;

bliver ikke reset.

public static int[] FindLargest(Func<T[], Tuple<bool,int>> f, params List<T>[] lists)
        {
            highscore = int.MinValue;
            int[] res = new int[lists.Length];
            int[] work = new int[lists.Length];
            FindLargest(f, lists, 0, work, res);
            return res;
        }

burde fixe det.

Men det er nok paenere at lave det non-static.
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester