Consider the following problem: given a set of intervals S = {(a_1, b_1), ..., (
ID: 3851282 • Letter: C
Question
Consider the following problem: given a set of intervals S = {(a_1, b_1), ..., (a_n, b_n)}, find the largest subset of disjoint intervals. Two intervals (a_1, b_1) and (a_2, b_2) are disjoint if they do not overlap other than at their endpoints; in other words, if b_1 lessthanorequalto a_2 or b_2 lessthanorequalto a_1. For example, if S = {(1, 5), (3, 6), (5, 7)}, then the largest subset of disjoint intervals is {(1, 5), (5, 7)}. While brainstorming, you and your friends come up with four greedy strategies for this problem. For each strategy, prove or disprove that it always produces an optimal solution. Assume that ties are broken arbitrarily. Pick the shortest interval (minimum b - a). Remove all intervals that overlap this interval. Repeat. Pick the interval with the minimum start (a-value). Remove all intervals that overlap this interval. Repeat. Pick the interval with the minimum end (b-value). Remove all intervals that overlap this interval. Repeat. Pick the interval that overlaps the fewest other intervals. Remove all intervals that overlap this interval. Repeat. Select one of the above strategies for which you were able to prove that it always produces an optimal solution. Give a greedy algorithm for this problem, based on your selected strategy. Analyze the running time of your algorithm.Explanation / Answer
e0let us take strategy (c)
GreedySchedule -
Initialize R to contain all intervals -
While R is not empty -
Choose an interval (S(i), F(i)) from R that has the smallest value of F(i) -
Delete all intervals in R that overlaps with (S(i), F(i))
f)
nLet and be sorted. By definition of OPT we have k m
nFact: for every i k, Ai finishes not later than Bi.
nPf. by induction.
nFor i = 1 by definition of a step in the algorithm.
nSuppose that Ai-1 finishes not later than Bi-1.
nFrom the definition of a step in the algorithm we get that Ai is the first interval that finishes after Ai-1 and does not verlap it.
nIf Bi finished before Ai then it would overlap some of the previous A1 ,…, Ai-1 and
nconsequently - by the inductive assumption - it would overlap Bi-1, which would be a contradiction.
nTheorem: A is the exact solution.
nProof: we show that k = m.
nSuppose to the contrary that k < m. We have that Ak finishes not later than Bk
nHence we could add Bk+1 to A and obtain bigger solution by the algorithm-contradiction
nSorting intervals according to the right-most ends
nFor every consecutive interval:
nIf the left-most end is after the right-most end of the last selected interval then we select this interval
nOtherwise we skip it and go to the next interval
n
nTime complexity: O(n log n + n) = O(n log n)