Egy művészeti galériában minden őr néhány folytonos időintervallumban van szolgálatban. Az őrzési Terv [T1(i),T2(i)] értékpárokat tartalmaz, melyek az i. őr szolgálati idejének kezdetét és végét jelentik. Egy őrzési Terv készítésekor a következőket kell végrehajtani:Feladat:
(a) Ellenőrizni kell, hogy a [0, Záróra] időintervallum bármely pillanatában legalább 2 őr legyen a galériában!Bemenet:
Ha az előző feltétel nem teljesül
(b) meg kell határozni az összes olyan intervallumot, amelyben az őrség hiányos (2-nél kevesebb őr van szolgálatban)
(c) Találd meg a kiegészítő őrök minimális számát úgy, hogy a szolgálati idő a megadottal egyenlő legyen!
(d) Keresd meg azt az őrzési összeállítást, melyhez nem szükséges kiegészítő őr! Változtasd meg bármelyik őr kezdési idejét úgy, hogy a szolgálat időtartama ne változzon!
(e) Ha az előző terv pont végrehajtható, készíts egy új őrzési Tervet, mely a lehető legkevesebb változtatást tartalmazza!(Minden időpont egész percekben van megadva.)Kimenet:
Záróra Az őrség munkaidejének vége.
A gelériát a [0, Záróra] intervallumban kell őrizniN Az őrök száma. T1[i], T2[i], i=1, ..., N Az i. őr szolgálati idejének kezdete és vége. Hossz A kiegészítő őrök szolgálati idejének előírt hossza. (1) Az (a) pontra adott válasz ("Igen" vagy "Nem").
(2) Ha az előző válasz "Nem", az időintervallumok listája, melyekben az őrség hiányos, valamint a szolgálatban levő őrök száma (0 vagy 1).
(3) A kiegészítő őrök száma, és szolgálati intervallumuk listája.
(4) A (d) pontban feltett kérdésre adott válasz ("Igen" vagy "Nem"). Ha ez a válasz "Igen", azon őrök sorszámai, melyek kezdési ideje megváltozott, és a megváltozott időpontok.
(5) Az (e) pontra adott válasz, azon őrök száma, melyek kezdési időpontja megváltozott, a sorszámuk és a megváltozott időpontok.