Data Structures and Algorithms

Thank you!

Suppose you are given a set T = {(si, f), . . . , (sn, f) of n tasks. where each task i is defined by the start time s, and a finish time fi. Two tasks t and t, are non-conflicting if f s or f, si. The activity selection problem asks for the largest number of tasks can be scheduled in a non-conflicting way. The greedy algorithm explained in class considers tasks one by one ordered by the finish time. Ordering by increasing finish time is crucial to prove that this strategy always leads to the optimal solution. Does the following greedy algorithm compute the optimal solution for activity selection? 1. Compute the number of overlaps for each task 2. Sort the task by the number of overlaps, in increasing order (break ties arbitrarily) 3. Pick the task i with the smallest number of overlaps, schedule it, and remove from further consideration tasks that are overlapping with i 4. Repeat step 3 until all tasks are scheduled Note that the number of overlaps is NOT updated after step 1. If you think the strategy works, prove that the greedy choice property hold. If not, show an example where this strategy gives a suboptimal solution. Suppose you are given a set T = {(si, f), . . . , (sn, f) of n tasks. where each task i is defined by the start time s, and a finish time fi. Two tasks t and t, are non-conflicting if f s or f, si. The activity selection problem asks for the largest number of tasks can be scheduled in a non-conflicting way. The greedy algorithm explained in class considers tasks one by one ordered by the finish time. Ordering by increasing finish time is crucial to prove that this strategy always leads to the optimal solution. Does the following greedy algorithm compute the optimal solution for activity selection? 1. Compute the number of overlaps for each task 2. Sort the task by the number of overlaps, in increasing order (break ties arbitrarily) 3. Pick the task i with the smallest number of overlaps, schedule it, and remove from further consideration tasks that are overlapping with i 4. Repeat step 3 until all tasks are scheduled Note that the number of overlaps is NOT updated after step 1. If you think the strategy works, prove that the greedy choice property hold. If not, show an example where this strategy gives a suboptimal solution