Gegeven zijn een reeks rechthoekige gebouwen die op een vlakte staan. We bekijken deze gebouwen in vooraanzicht en verkrijgen zo een tweedimensionale projectie waarbij de contouren van de gebouwen op zekere plaatsen overlappen. Figuur 1 toont een voorbeeld met vijf gebouwen (in het blauw). We willen de gemeenschappelijke contour van alle gebouwen samen berekenen, zoals ook aangegeven op de figuur in rode stippellijn, en noemen dit de skyline.

Gegeven zijn twee eenvoudige klassen Gebouw¹ en SkylinePunt². De eerste wordt gebruikt om de gegeven gebouwen voor te stellen. Aan een gebouw kan je de linker- en rechtercoördinaat \(l\) en \(r\), respectievelijk, en hoogte \(h\) opvragen. De tweede klasse wordt gebruikt om de skyline voor te stellen. Deze bestaat uit een lijst van skyline punten die aangeven op welke \(x\)-coördinaat de hoogte \(h\) van de skyline verandert. De skyline uit bovenstaande figuur wordt voorgesteld door de volgende lijst punten:

\[[(2, 18), (12, 0), (17, 15), (22, 28), (29, 5), (30, 0)]\]

De skyline begint bij de linkercoördinaat van het meest linkse gebouw, op de hoogte van dit gebouw, en eindigt bij de rechtercoördinaat van het meest rechtse gebouw, op hoogte nul. De \(x\)-coördinaten van opeenvolgende skyline punten zijn strikt stijgend en de skyline bevat geen overtollige punten, d.w.z. er komt precies één punt voor enkel daar waar de hoogte effectief verandert.

Het is verplicht om een verdeel-en-heers algoritme te ontwikkelen. Implementeer daartoe de interface Skyline³ in een klasse MySkyline. Elk van de gevraagde methoden kan je apart testen op Dodona, ook als de andere nog niet af zijn. Gooi bijvoorbeeld een UnsupportedOperationExeption in de methoden die je nog niet geïmplementeerd hebt.

1. Schrijf de methode List<SkylinePunt> gebouw(Gebouw gebouw). Deze berekent de skyline die hoort bij één gebouw.

2. Schrijf de methode List<SkylinePunt> skyline(List<Gebouw> gebouwen). Deze bevat het verdeel-en-heers algoritme dat de skyline van een reeks gebouwen berekent door gebruik te maken van de methode gebouw en merge. De methode merge laat je op dit moment nog leeg. Wanneer je indient wordt namelijk een bestaande correcte merge-implementatie ingeplugd. Na deze stap zou je ook moeten slagen voor de tweede categorie testen op Dodona.

3. Voorzie tenslotte een eigen implementatie voor de methode List<SkylinePunt> merge(List<SkylinePunt> s1, List<SkylinePunt> s2) die de samenvoeging van twee skylines berekent. Deze volgt de maximale hoogte van beide afzonderlijke skylines. Wanneer je zelf een correcte merge hebt geïmplementeerd, zouden de overige testen op Dodona ook moeten slagen.

Dien na elke stap je oplossing in. Ga pas verder met de volgende stap als de testen voor alle voorgaande stappen slagen. Gebruik eventueel de testklasse Simpletest⁴ om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.