מבחן 2/7/2009 שאלה 4
lihi (guest) 07 Feb 2012 10:20
תארו אלגוריתם יעיל ככל האפשר המקבל רשימה של m דרישות ובודק האם קיים אוסף של n קטעים פתוחים לא ריקים בישר R,
Ik=(ak,bk) עבור k=1,2,3,…,n המקיים את כל הדרישות.
קיימים שני סוגים של דרישות:
1. הקטע Ii נמצא כולו מימין לקטע Ij
2. הקטעים Ii ו-Ij נחתכים.
דוגמא לקלט שעבורו האלגוריתם יחזיר false:
א) I1 כולו מימין לI2 ב) I2 כולו מימין לI3 ג) I1 ו I3 נחתכים
דוגמא לקלט שיחזיר true:
ג) I1 ו I2 נחתכים ג) I1 ו I3 נחתכים א) I2 כולו מימין לI3
חשבתי על מיון טופולוגי אבל לא הצלחתי למצוא דרך לחבר את צמתי הגרף בצורה טובה… רעיונות?
