CIO Tech Eksperten IT-JOB IT-Kurser Events Podcast Søg

Log ind eller opret profil

Du kan også logge ind via nedenstående tjenester

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

Synes godt om

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

Synes godt om

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

Synes godt om

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..

Synes godt om

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

Synes godt om

1 synes godt om dette

lasserasch Juniormester

24. oktober 2017 - 10:09 #5

Super Arne. Mange tak for input. Det vil jeg forsøge at implementere her i dag. :-) :-)

Synes godt om

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();

Synes godt om

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.

Synes godt om

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.

Følg dette spørgsmål

Opret Preview

Se alle it-kurser fra Computerworld Kurser

IT-kurser om Microsoft 365, sikkerhed, personlig vækst, udvikling, digital markedsføring, grafisk design, SAP og forretningsanalyse.

Se alle it-kurser

Flere spørgsmål fra C# kategorien

Titel	Indlæg	Oprettet	Seneste aktivitet
Regex Af joki i C#	8	21/10/202408:36	23/10/202414:35
Søger programmør til hjælp på eksamensprojekt - betaler gerne! Af Caroline BJ i C#	0	12/06/202411:19	-
Drev bogstav som path Af prox1 i C#	5	01/05/202403:58	01/05/202421:24
Tråd programmering Af lasserasch i C#	3	04/12/202313:03	06/01/202419:04
Inspiration til GUI opdatering fra Service lag. Af lasserasch i C#	2	28/11/202308:48	28/11/202319:29

Se alle spørgsmål i kategorien Opret spørgsmål

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

Alle kategorier på Eksperten

Seneste artiklerRSS