יש לי קלט של פעילויות {1,2....n} -עם זמני התחלה s_k וזמני סיום f_k עבור כל קטע j. אני מחפש פתרון בזמן הכי יעיל שאפשר( nlogn זה מצויין..) לבעיה הבאה:

נסמן ב- p(j) לכל פעילות j, פעילות המתחילה מאוחר ביותר מבין כל הפעילויות בקלט המסתיימות לא אחרי s_j .(אם לא קיימת פעילות כזו p(j)=0).

אני צריך למצוא את p(j) לכל j.

----

אם למשל במקום הקטע המודגש היה כתוב "מסתיימת" היה ניתן לעשות זאת באמצעות עץ חיפוש הממויין לפי זמני סיום ועבור כל וכל p(j) ניתן למצוא ב logn וסהה"כ nlogn.

אך במקרה שלי קצת נתקעתי.

מה? הניסוח שלך מאוד לא ברור. אתה יכול לנסח את הבעיה בצורה קצת יותר ברורה? מה זה (p(j?

ערכתי קצת, אבל לא הבנתי מה לא ברור...

האם חשבת בכיוון של לבנות שני עצי חיפוש, אחד לפי זמני התחלה ואחד לפי זמני סיום? כמובן שתצטרך לדעת איזה צומת בעץ הראשון מתאים לצומת בעץ השני ואז תהליך החיפוש שלך יהיה מורכב ממעבר בין העצים.