Here is a description of the Interval Scheduling Problem. You have a set S of n
ID: 3569548 • Letter: H
Question
Here is a description of the Interval Scheduling Problem. You have a set S of n requests, S = {1, 2, ...n}. Each request i corresponds to an interval of time that starts at s(i) and finishes at f(i). A subset A of S is compatible if no two requests overlap in their time intervals. The problem is how to select a compatible subset A that contains the maximum number of requests. Because we want to maximize the number of requests (an optimization problem), we try a greedy strategy of filling A with requests that have the smallest time interval requirements so that we can fit the most in. Here is pseudocode for an algorithm using this strategy. Set A to the empty set While S is not empty Add to A the request i in S with the smallest time interval Remove all requests from S with time intervals incompatible with i Return A Either prove that this algorithm always gives an optimal solution or give an example where it fails to give an optimal solution.Explanation / Answer
Claim : Choosing request with smallest time interval will not give an optimal solution always.
Proof -> in case if we choose such request and let this request overlap with n other request we can not any of these n request. in such case we will never have optimal solution if we choose the smallest time interval.
Optimal Solution : sort the request with ending point in ascending order.
Pseudo Code ->
while requests R is not empty:
Choose an interval (S(i), F(i)) from requests (R) that has the smallest value of F(i) pick first
Delete all intervals in R that overlap with (S(i), F(i))
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.