פורסם 2012 במאי 413 שנים יש לי קלט של פעילויות {1,2....n} -עם זמני התחלה s_k וזמני סיום f_k עבור כל קטע j. אני מחפש פתרון בזמן הכי יעיל שאפשר( nlogn זה מצויין..) לבעיה הבאה:נסמן ב- p(j) לכל פעילות j, פעילות המתחילה מאוחר ביותר מבין כל הפעילויות בקלט המסתיימות לא אחרי s_j .(אם לא קיימת פעילות כזו p(j)=0).אני צריך למצוא את p(j) לכל j.----אם למשל במקום הקטע המודגש היה כתוב "מסתיימת" היה ניתן לעשות זאת באמצעות עץ חיפוש הממויין לפי זמני סיום ועבור כל וכל p(j) ניתן למצוא ב logn וסהה"כ nlogn.אך במקרה שלי קצת נתקעתי.
פורסם 2012 במאי 413 שנים מה? הניסוח שלך מאוד לא ברור. אתה יכול לנסח את הבעיה בצורה קצת יותר ברורה? מה זה (p(j?
פורסם 2012 במאי 413 שנים האם חשבת בכיוון של לבנות שני עצי חיפוש, אחד לפי זמני התחלה ואחד לפי זמני סיום? כמובן שתצטרך לדעת איזה צומת בעץ הראשון מתאים לצומת בעץ השני ואז תהליך החיפוש שלך יהיה מורכב ממעבר בין העצים.
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.