For part b, pseudo-code is encouraged. Consider a scheduling problem in which yo

Question

For part b, pseudo-code is encouraged.

Consider a scheduling problem in which you are given a list of events for a given day, you have 1 room in which to schedule them. The times for some events are overlapping, so you cannot schedule them all and you cannot partially schedule a event. You will get a portion of the proceeds for each event scheduled based on attendance, thus your task is to maximize your profit. PROBLEM: E = list of events e1, e2, ...., en For each event ek, it has profit pk, start time sk, and finish time fk (times are in integer units). a) Provide a recursive definition of the solution using m[ij] = maximum profit for some list of events designated by "i" and some time constraint designated by "j". Consider the events ordered by increasing finish time. The latest finish time is then fn. M[i, j] = b) Write the recursive algorithm (memoized version) to solve this scheduling problem and provide the runtime bound.

Explanation / Answer

Firstly, the jobs are to be scheduled according to the finish time. Then the recursive process can be applied. Considering array A[] holds for 'n' number of jobs forMax(A[], n) { if (n==1) then return A[0]; Return the maximum of following two jobs. (i) Maximum of the jobs by excluding current scheduled job, forMax(A, n-1) (ii) Maximum by including the current scheduled job }

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.