Consider the interval scheduling problem we studied in class: Given a sequence o
ID: 3792797 • Letter: C
Question
Consider the interval scheduling problem we studied in class: Given a sequence of requests with start and finish times (s (i), t(i)), i n, find a set of non-conflicting jobs of maximum possible size. Show that the following algorithm solves the problem correctly (i.e., returns a set of non-conflicting jobs of maximum size) LATEST START TIME (LST): (a) Set R 11, ...,n), and A O. (b) While RE i. Pick request i ER with the latest start time. ii. Add i to A. iii. Remove all requests that conflict with i (including i) from R c) RETURN AExplanation / Answer
The proof of correctness of the algorithm is trivial. Since, at the begining when a task is selected for scheduing that has the latest (or earliest) start time and any other task that is having conflict with the selected tsk is removed from the set. Thus, there cannot be any conflict. but it may not be optimal because of its greedy solving nature it can be stuck in some local minima instead of achieveing the global minima. In other words, the selection rule is fixed where the job with earliest start time is selected first but there may be some optimal solution possible in which other job may be selected first.