Ortaokul Bilgisayar Olimpiyatı 2019, 1. Aşama, Soru 20

## [16-20 soruları için açıklama]
Bir bilgisayar tamircisi o gün içerisinde hangi bilgisayarları tamir edeceğine bir gün öncesinden kendisine verilen taleplerdeki bilgisayar geliş saatleri ve tamirin ne kadar süreceği bilgisini kullanarak karar vermektedir. Aynı anda sadece bir bilgisayar tamir edebildiğinden ve bir bilgisayar gelir gelmez tamire başlamak istediğinden, kendisine gelen talepler içinden bazılarını reddetmek zorunda kalmaktadır. Çünkü bilgisayar geliş saati ve tamir bitiş saatleri örtüşen iki bilgisayar varsa bunlardan sadece bir tanesini seçebilir.
Örnek vermek gerekirse, gelen talepler:
A: sabah 9’da gelecek ve tamir 2 saat sürecek
B: sabah 10’da gelecek ve tamir yarım saat sürecek
C: sabah 11’de gelecek ve tamir 3 saat sürecek
ise tamirci A ve B bilgisayarlarından birisini reddetmek zorundadır. Yani o günün tamir planında ya A ve C olacaktır ya da B ve C olacaktır.
Tamircinin hedefi o gün içerisinde en fazla sayıda bilgisayar tamir etmek olduğundan tamirci için aşağıdaki gibi bir algoritma tasarladık:
1. Bilgisayarları tamir bitiş zamanlarına göre küçükten büyüğe sırala. Bu sıralamaya göre sıralanmış bilgisayarlara A1, A2, .. An  diyelim.
2. A1’i o günkü tamir planına ekle.
3. 2. bilgisayardan n. bilgisayara kadar sıra ile aşağıdaki işlemi gerçekleştir:
Eğer sıradaki bilgisayarın geliş saati plana en son eklenmiş bilgisayarın bitiş saatinden sonra ise sıradaki bilgisayarı tamir planına ekle, değil ise bilgisayarın sahibine bilgisayarının tamirinin o gün yapılamayacağını bildir.
Bu verilen algoritma, o gün için karşılanabilecek en fazla talep sayısında talebi plana koyar. Bu algoritmayı yukarıdaki örneğe uyguladığımızda bilgisayarlar tamir bitiş saatlerine göre B, A, C olarak sıralanacaklar ve algoritmamız B ve C bilgisayarlarını o gün tamir edilecek bilgisayarlar olarak 
belirleyecektir. 

---

Aşağıda verilen tamir taleplerini göz önüne aldığımızda ve verilen algoritma uygulandığında, A4 ve A5 no'lu taleplerin tamir planında yer almaması için en sondaki A8 talebinin başlangıç saati ve süresi şıklarındakinden hangisi olabilir?
<table><tr><td></td><td>A1</td><td>A2</td><td>A3</td><td>A4</td><td>A5</td><td>A6</td><td>A7</td><td>A8</td></tr><tr><td>Geliş saati</td><td>8:00</td><td>7:00</td><td>10:00</td><td>12:00</td><td>15:00</td><td>14:00</td><td>13:00</td><td>?</td></tr><tr><td>Tamir süresi (saat)</td><td>3</td><td>2</td><td>1.5</td><td>3</td><td>1</td><td>3</td><td>4.5</td><td>?</td></tr></table>

Şıklar:
A) 11:00 ve 4.5 saat | B) 13:00 ve 2.5 saat | C) 13:00 ve 3 saat | D) 12:00 ve 3.5 saat | E) Hem A4 hem de A5'in planda olmamasını sağlayan bir talep mümkün değildir

Cevap: E Hem A4 hem de A5'in planda olmamasını sağlayan bir talep mümkün değildir

Çözüm:
A4 ve A5 birbirleri ile örtüşmeyen ve hemen birbiri ardına gerçekleşen ve algoritma uygulandığında planda yer alacak, (A2,A3,A4,A5), taleplerdir. A4'ün planda yer almaması için A8 talebinin algoritmaya göre pnden önce işlenmesi yani A4'ün bitiş zamanından önce bitmesi gerekmektedir. A4'ün bitiş zamanı A5'in seçilmesini engellemediği için A4'ten önce biten bir talebin de A5'i engellemesi mümkün değildir. Bu durumda hem A4 hem de A5'i engelleyecek bir talep yapılması imkansızdır. Cevap E şıkkı olur.