Let S = ?, ?? ??. , ao be a set with n-10 acti ities. The start time and the fin

Question

Let S = ?, ?? ??. , ao be a set with n-10 acti ities. The start time and the finish time of each activity is shown in the table below. Apply the GREEDY-ACTIVITY-SELECTOR function learned in class. What is the subset of activities returned? Write the activities in the correct order in which they are selected by the algorithm. Si f a2 4 13 ?? 11215 as 1 5 a69 11 a7 1014 ag 1315 a10 6 11 Hint: Read carefully the "Note" after the GREEDY-ACTIVITY-SELECTOR function in Module 8.3.pdf "If they (the activities) are not sorted then we have to sort them first".

Explanation / Answer

The GREEDY-ACTIVITY-SELECTOR works by selecting the activity which has the least finishing time(call P1), next with the second least finishing time(call P2) (given that the starting time is greater than the finish time of P1) and so on. So let us first sort our activities in increasing order of finish time, and if equal finish time then sort in increasing starting time.

So the order of activities selected are { a1, a3, a4, a6, a9} The correct order in which they're selected are:
1. a4 [1:3]
2. a1 [3:7]
3. a9 [7:8]
4. a6 [9:11]
5. a3 [12:15]

si fi a4 1 3 a5 1 5 a1 3 7 a9 7 8 a10 6 11 a6 9 11 a2 4 13 a7 10 14 a3 12 15 a8 13 15

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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