Büyük bir bilgisayar sistemini izlemeye yardımcı olan bir grup güvenlik danışmanı ile çalışıyorsunuz. “Yüksek öncelikli” olarak belirlenmiş süreçlerin izlenmesine özellikle dikkat ediliyor. Her bir bu tür süreç, önceden planlanmış bir başlangıç ve bitiş zamanına sahiptir. Danışmanlar, gün boyunca çalışacak olan 1’den n’ye kadar numaralandırılmış n tane “yüksek öncelikli” sürecin başlangıç ve bitiş zamanlarını biliyorlar. j. yüksek öncelikli sürecin başlangıç ve bitiş zamanları sⱼ ve fⱼ ile ifade edilsin ve bu süreç [sⱼ, fⱼ] zaman aralığında sürekli çalışsın. A[1..n] dizisinin j. elemanı, j. yüksek öncelikli sürecin çalıştığı zaman aralığını göstersin.
Danışmanlar ilk olarak, çalıştırıldığında çok kısa bir süre (anlık) çalışan ve o anda sistemde çalışan her yüksek öncelikli sürecin çeşitli bilgilerini kaydeden “Kontrol” adında bir program yazıyorlar. Kontrol programının her çalıştırılması bir “an” (zaman aralığı değil) olarak modellenmektedir. T[1..m] dizisi, m tane “an” içeren bir dizi olsun. Kontrol programı yalnızca T[1..m] dizisinde verilen anlarda çalıştırılabilmektedir.
Danışmanlar, Kontrol programının gün boyunca her yüksek öncelikli sürecin zaman aralığı sırasında en az bir kez çalıştırıldığından emin olmak ve aynı zamanda Kontrol programının toplam çalıştırılma sayısını en aza indirmek istiyorlar. Bunun için şu strateji düşünülmektedir: Başlangıçta tüm yüksek öncelikli süreçler “işaretlenmemiş” kabul edilir. En fazla işaretlenmemiş yüksek öncelikli süreç aralığı tarafından içerilen T[i] anında Kontrol programı çalıştırılır ve sonra bu anı içeren süreçler işaretlenir. İşaretlenmemiş süreç kalmayana kadar bu işlem tekrarlanır. Bu stratejinin her zaman Kontrol programının çalıştırılma sayısını en aza indirmeyeceğini hangi A ve T dizi çifti örnek göstererek ispatlayabiliriz?