[PHP] Tijdvakken genereren op basis van multilevel array

[Online-Gamer]

Hallo,

Ik ben op dit moment bezig met een afspraken systeem in combinatie met een extern systeem.
Het moet hierbij mogelijk zijn om afspraken te maken voor "producten", je moet dan denken aan een soort winkelwagen waarbij je producten meerdere keren kunt selecteren. Elk product heeft zijn eigen afspraak-lengte. Stel dat ik dit in mijn winkelwagen heb:

A0010 x1 (afspraak lengte = 5 minuten dus 5 minuten in totaal)
A0004 x2 (afspraak lengte = 10 minuten dus 20 minuten in totaal)

Via de API van het externe systeem kan ik alleen de beschikbare dagen en tijden opvragen PER product.
Voor deze 2 producten krijg ik dan bijvoorbeeld de volgende data terug (het zijn eigenlijk timestamps maar dit is wat duidelijker):

code:

Array
(
    [A0004] => Array
        (
            [0] => 30-10-2014 09:20:00
            [1] => 30-10-2014 09:30:00
            [2] => 30-10-2014 15:20:00
            [3] => 30-10-2014 15:30:00
            [4] => 30-10-2014 16:30:00
            [5] => 30-10-2014 17:10:00
            [6] => 30-10-2014 17:20:00
            [7] => 30-10-2014 17:30:00
            [8] => 30-10-2014 18:10:00
            [9] => 30-10-2014 18:20:00
            [10] => 30-10-2014 18:30:00
            [11] => 31-10-2014 09:00:00
            [12] => 31-10-2014 09:10:00
            [13] => 31-10-2014 09:20:00
            [14] => 31-10-2014 12:20:00
            [15] => 03-11-2014 09:10:00
            [16] => 03-11-2014 09:20:00
            [17] => 03-11-2014 09:30:00
            [18] => 03-11-2014 10:10:00
            [19] => 03-11-2014 10:20:00
            [20] => 03-11-2014 12:10:00
            [21] => 03-11-2014 12:20:00
            [22] => 03-11-2014 12:30:00
            [23] => 03-11-2014 13:00:00
            [24] => 03-11-2014 13:10:00
            [25] => 03-11-2014 13:20:00
            [26] => 03-11-2014 14:00:00
            [27] => 03-11-2014 14:10:00
            [28] => 03-11-2014 14:20:00
            [29] => 03-11-2014 14:30:00
            [30] => 03-11-2014 15:10:00
            [31] => 03-11-2014 15:20:00
            [32] => 03-11-2014 15:30:00
            [33] => 03-11-2014 16:00:00
            [34] => 03-11-2014 16:10:00
            [35] => 03-11-2014 16:20:00
            [36] => 03-11-2014 16:30:00
            [37] => 03-11-2014 17:00:00
            [38] => 03-11-2014 17:10:00
            [39] => 03-11-2014 17:20:00
        )
    [A0010] => Array
        (
            [0] => 29-10-2014 15:15:00
            [1] => 29-10-2014 15:40:00
            [2] => 29-10-2014 16:35:00
            [3] => 29-10-2014 16:40:00
            [4] => 29-10-2014 17:10:00
            [5] => 29-10-2014 17:15:00
            [6] => 29-10-2014 17:20:00
            [7] => 29-10-2014 17:40:00
            [8] => 30-10-2014 09:20:00
            [9] => 30-10-2014 09:25:00
            [10] => 30-10-2014 09:30:00
            [11] => 30-10-2014 09:35:00
            [12] => 30-10-2014 09:40:00
            [13] => 30-10-2014 10:10:00
            [14] => 30-10-2014 10:25:00
            [15] => 30-10-2014 10:40:00
            [16] => 30-10-2014 11:05:00
            [17] => 30-10-2014 11:40:00
            [18] => 30-10-2014 12:25:00
            [19] => 30-10-2014 12:40:00
            [20] => 30-10-2014 13:40:00
            [21] => 30-10-2014 14:10:00
            [22] => 30-10-2014 14:40:00
            [23] => 30-10-2014 15:20:00
            [24] => 30-10-2014 15:25:00
            [25] => 30-10-2014 15:30:00
            [26] => 30-10-2014 15:35:00
            [27] => 30-10-2014 15:40:00
            [28] => 30-10-2014 16:15:00
            [29] => 30-10-2014 16:20:00
            [30] => 30-10-2014 16:30:00
            [31] => 30-10-2014 16:35:00
            [32] => 30-10-2014 16:40:00
            [33] => 30-10-2014 17:10:00
            [34] => 30-10-2014 17:15:00
            [35] => 30-10-2014 17:20:00
            [36] => 30-10-2014 17:25:00
            [37] => 30-10-2014 17:30:00
            [38] => 30-10-2014 17:35:00
            [39] => 30-10-2014 17:40:00
            [40] => 30-10-2014 18:05:00
            [41] => 30-10-2014 18:10:00
            [42] => 30-10-2014 18:15:00
            [43] => 30-10-2014 18:20:00
            [44] => 30-10-2014 18:25:00
            [45] => 30-10-2014 18:30:00
            [46] => 30-10-2014 18:35:00
            [47] => 30-10-2014 18:40:00
            [48] => 30-10-2014 19:15:00
            [49] => 30-10-2014 20:40:00
            [50] => 31-10-2014 09:00:00
            [51] => 31-10-2014 09:05:00
            [52] => 31-10-2014 09:10:00
            [53] => 31-10-2014 09:15:00
            [54] => 31-10-2014 09:20:00
            [55] => 31-10-2014 09:25:00
            [56] => 31-10-2014 09:40:00
            [57] => 31-10-2014 10:25:00
            [58] => 31-10-2014 10:35:00
            [59] => 31-10-2014 11:35:00
            [60] => 31-10-2014 11:40:00
            [61] => 31-10-2014 12:20:00
            [62] => 31-10-2014 12:25:00
            [63] => 03-11-2014 09:05:00
            [64] => 03-11-2014 09:10:00
            [65] => 03-11-2014 09:15:00
            [66] => 03-11-2014 09:20:00
            [67] => 03-11-2014 09:25:00
            [68] => 03-11-2014 09:30:00
            [69] => 03-11-2014 09:35:00
            [70] => 03-11-2014 09:40:00
            [71] => 03-11-2014 10:05:00
            [72] => 03-11-2014 10:10:00
            [73] => 03-11-2014 10:15:00
            [74] => 03-11-2014 10:20:00
            [75] => 03-11-2014 10:25:00
            [76] => 03-11-2014 10:40:00
            [77] => 03-11-2014 11:25:00
            [78] => 03-11-2014 11:40:00
            [79] => 03-11-2014 12:05:00
            [80] => 03-11-2014 12:10:00
            [81] => 03-11-2014 12:15:00
            [82] => 03-11-2014 12:20:00
            [83] => 03-11-2014 12:25:00
            [84] => 03-11-2014 12:30:00
            [85] => 03-11-2014 12:35:00
            [86] => 03-11-2014 12:40:00
            [87] => 03-11-2014 13:00:00
            [88] => 03-11-2014 13:05:00
            [89] => 03-11-2014 13:10:00
            [90] => 03-11-2014 13:15:00
            [91] => 03-11-2014 13:20:00
            [92] => 03-11-2014 13:25:00
            [93] => 03-11-2014 13:35:00
            [94] => 03-11-2014 13:40:00
            [95] => 03-11-2014 14:00:00
            [96] => 03-11-2014 14:05:00
            [97] => 03-11-2014 14:10:00
            [98] => 03-11-2014 14:15:00
            [99] => 03-11-2014 14:20:00
        )
)
1

Met de informatie hierboven zou ik dus een aaneengesloten tijdvak moeten genereren met deze 2 producten (3 in aantal).
Opmerking: het is dus mogelijk om meer dan 2 producten hebben, en ook meer dan 2 in aantal.

Er zal dus iets moeten komen wat op 1 of andere manier de tijdvakken van de meerdere producten aan elkaar kan koppelen (waarbij er per product ook aaneensluitende vakken moeten zijn wanneer je er meerdere van selecteert), maar ik heb geen idee hoe ik dat kan aanpakken.
Ik heb zelf geprobeerd om bij product 1 te beginnen en per tijd te kijken of er een aansluitend vak van een ander product is, maar dit was totaal niet flexibel met meerdere producten en liep ook gelijk uit z'n geheugen met de vele foreaches.

Heb me rot gezocht op google maar kon niets vinden voor dit specifieke probleem.
Heeft iemand enig idee hoe ik dit aan zou kunnen pakken?

Alvast bedankt!

[Rushleader]

Hey, wat je zou kunnen proberen is initieel voor het product met de langste duur (product 1) alle werkbare tijdvakken te vinden. Daarna per tijdvak van product 1 kijk je of er voor product 2 een aansluitend tijdvak bestaat.
Nee? Dan test je het volgende tijdvak van product 1 enz...

--edit

In jouw geschetste situatie zou A0004 dus product 1 zijn

[ Voor 11% gewijzigd door Rushleader op 30-10-2014 11:53 ]

[xleeuwx]

Altijd leuke uitdaging, het makkelijkst is om de datums met tijden op te slaan in je DB per product, daarna kan je vergelijkingen maken (zet in je DB wel begin en eindtijd, zo kan je makkelijker rekenen. Daarna kan je een afspraak inplannen op een timeslotID, wat natuurlijk ook weer makkelijk terug te vinden is

[Joolee]

Ik denk dat het sowieso handig is alle aansluitende tijdvakken van een product eerst samen te voegen, dat scheelt daarna een hoop operaties. Dan kun je de tijd_start en tijd_end los opslaan zodat je wat makkelijker overlappende tijdvakken kunt vinden.
In een SQL query is dat relatief eenvoudig dmv een self join met between op zowel tijd_start als tijd_end te doen. In PHP zul je loops in loops moeten plaatsen vrees ik.
Eventueel kun je wel optimaliseren door bijv. per dag een array met tijdvakken te maken zodat je niet door alle beschikbare tijdvakken heen hoeft te lopen. Alle tijdvakken welke te kort zijn om aan de eisen te voldoen kun je bij de eerste stap al weglaten.

* Joolee is geen algoritme expert...

[ Voor 7% gewijzigd door Joolee op 30-10-2014 12:06 ]

[Janoz]

* Janoz is wel een algoritme expert en het eerste dat in mij opkomt is dat het vak op de opleiding vaak algoritmen en datastructuren heet. Enkel met deze maps* werken is lastig. Het is denk ik makkelijker om dit om te zetten.

Als het bijvoorbeeld verplicht aansluitend moet zijn zou je een gerichte graaf kunnen maken waarbij elke afspraak een node is en elke opvolgende afspraak vervolgens een verbinding heeft. Je begint dan met je lijstje gevraagde afspraken. Kiest een startpunt en doorloopt de graaf (je maakt een stap naar de volgende node wanneer die afspraak in je lijst voorkomt en haalt hem vervolgens uit de lijst) net zo lang tot je niet verder kunt omdat er geen verbinding meer is naar een node die in je lijst voorkomt (dan moet je terug om een ander pad te bewandelen) of je lijst is leeg en dan heb je een lijstje aansluitende afspraken.


_{* (bij php kunnen ze het wel zeggen, maar de rest van de wereld noemt het gewoon maps. Zolang je dat in je achterhoofd houdt kun je de literatuur ook beter plaatsen )}

[Online-Gamer]

Heel erg bedankt voor de reacties!
Ik heb het nu op de volgende manier opgelost:
Eerst worden de tijdvakken per product bepaald, bij een aantal van 2 per product wordt er dus eerst gezocht naar aaneensluitende vakken en worden de onbruikbare vakken eruit gefiltert.

Vervolgens worden de tijdvakken per product in een tijdelijke tabel gezet.
Daarna wordt er voor het eerste product gekeken naar het eerste tijdvak, vervolgens wordt er gekeken of het 2e product hier achter of voor past, past dit dan wordt er gekeken of het volgende product er achter of voor past enzovoort. Ik moet zeggen dat de snelheid me alles meevalt, het enige wat traag gaat zijn de API calls naar het externe systeem maar daar is vrij weinig aan te doen.

Nogmaals bedankt!