Een algoritmepuzzel voor het weekend

Stel: je opdrachtgever heeft een apparaat dat filmpjes afspeelt. Je hebt ervoor gezorgd dat de filmpjes worden afgespeeld op volgorde van een XML, waarin staat welk filmpje er wanneer moet worden gestart:

<playlist>
 <item id="1">
  <start_time>2010-03-18 0900</start_time>
  <end_time></end_time>
 </item>
 <item id="2">
  <start_time>2010-03-19 0900</start_time>
  <end_time>2010-03-19 1000</end_time>
 </item>
 <item id="3">
  <start_time>2010-03-19 1015</start_time>
  <end_time>2010-03-19 1115</end_time>
 </item>
 <item id="4">
  <start_time>2010-03-19 1100</start_time>
  <end_time></end_time>
 </item>
</playlist>

Regels zijn hierbij: eindtijd (<end_time/>) geldt alleen als er niet een ander filmpje wordt gestart voor de betreffende eindtijd. Als er op het tijdstip van de eindtijd geen filmpjes meer zijn om te spelen, dan blijft het filmpje spelen totdat er (ooit) een ander filmpje wordt gestart. Een item hoeft geen eindtijd te hebben.

Volgens bovenstaande XML zal de speler op 18 maart om 9 uur beginnen met item 1. Op 19 maart om 9 uur start item 2. Om 10 uur wil item 2 stoppen, dus begint item 1 weer te spelen. Om 10:15 begint item 3. Alhoewel item 3 pas wil eindigen om 11:15, begint item 4 om 11 uur. Item 4 blijft vervolgens net zolang doorspelen totdat er een nieuw item wordt toegevoegd of de player crasht. Whichever comes first.

Maar nu het probleem.

De opdrachtgever wil graag per dag zien wat er te spelen valt. Het overzicht is simpel: toon alle items die vandaag starten. Denk je.

Maar de opdrachtgever wil ook weten welke items er op de gekozen dag spelen, die eerder waren gestart. Zelfs items die eerder zijn gestart, maar op de gekozen dag niet te zien zijn, maar mogelijk in de toekomst nog wel moeten worden getoond.

De opdracht voor deze puzzel luidt: schrijf een methode die een juist overzicht maakt op basis van de beschreven regels voor het afspelen en de wensen van de opdrachtgever. Het overzicht moet kloppen voor elke willekeurige (geldige) playlist die wordt aangedragen.

Goed weekend!

UPDATE: voorbeeld van een playlist