שאלה ממבחן
tbar 15 Feb 2010 10:36
השאלה לקוחה מסמסטר א' , מועד ב', תשס"ן
16.10.06
פרופ חנוך לוי, עודד שוורץ
נתונים
n
קטעים על הישר
(כלומר הקלט הוא
n
זוגות (x,y) של נקודות התחלה וסיום
)
קטע יקרא "מרכזי" אם יש לפחות
n/4
קטעים שמתחילים לפניו (נקודת ההתחלה שלהם משמאל לנקודת ההתחלה שלו) וגם יש לפחות
n/4
קטעים שמסתיימים אחריו (נקודת הסיום שלהם מימין לנקודת הסיום שלו).
הציעו אלגוריתם שמחזיר את מספר הקטעים המרכזיים, בזמן ריצה
W.C.
הטוב ביותר שתוכלו.