2. In this question we consider the interval scheduling problem, as covered in class. (a) Consider a greedy algorithm which always selects the shortest appointment first. Draw an example with at least 5 appointments where this algorithm fails. List the order in which the algorithm selects the intervals, and also write down a larger subset of non-overlapping intervals than the subset output by the greedy algorithm. A comment on level of justification (applies to all of problems 2 and 3): to help us understand your thinking, it is worth writing a little about the order in which the algorithm selects the intervals. For example The algorithm takes intervals in the order [1,3,4]: first the algorithm takes interval 1 because that is the shortest. Interval 1 conflicts with intervals 2 and 5, so they are removed. The next shortest is 3, which conflicts with interval 6, and the only remaining interval is 4. YOUR ANSWER HERE. Weve provided you with some sample code to draw such a figure natively in LATEX, you just need to modify the start/end points and possibly add more intervals if you need (as well as answer the rest of the question!).

(b) Consider a greedy algorithm which always selects the longest appointment first. Draw an example with at least 5 appointments where this algorithm fails. Show the order in which the algorithm selects the intervals, and also show a larger subset of non-overlapping intervals than the subset output by the greedy algorithm. The same comments apply here as for 2a in terms of level of explanation.

2. In this question we consider the interval scheduling problem, as covered in class. (a) Consider a greedy algorithm which always selects the shortest appointment first. Draw an example with at least 5 appointments where this algorithm fails. List the order in which the algorithm selects the intervals, and also write down a larger subset of non-overlapping intervals than the subset output by the greedy algorithm. A comment on level of justification (applies to all of problems 2 and 3): to help us understand your thinking, it is worth writing a little about the order in which the algorithm selects the intervals. For erample "The algorithm takes intervals in the order (1,3,4): first the algorithm takes interval 1 because that is the shortest. Interval 1 conflicts with intervals 2 and 5, so they are removed. The nert shortest is 3, which conflicts with interval 6, and the only remaining interval is 4." YOUR ANSWER HERE. We've provided you with some sample code to draw such a figure natively in LATEX, you just need to modify the start/end points and possibly add more intervals if you need as well as answer the rest of the question!). (b) Consider a greedy algorithm which always selects the longest appointment first. Draw an example with at least 5 appointments where this algorithm fails. Show the order in which the algorithm selects the intervals, and also show a larger subset of non-overlapping intervals than the subset output by the greedy algorithm. The same comments apply here as for 2a in terms of level of explanation. 2. In this question we consider the interval scheduling problem, as covered in class. (a) Consider a greedy algorithm which always selects the shortest appointment first. Draw an example with at least 5 appointments where this algorithm fails. List the order in which the algorithm selects the intervals, and also write down a larger subset of non-overlapping intervals than the subset output by the greedy algorithm. A comment on level of justification (applies to all of problems 2 and 3): to help us understand your thinking, it is worth writing a little about the order in which the algorithm selects the intervals. For erample "The algorithm takes intervals in the order (1,3,4): first the algorithm takes interval 1 because that is the shortest. Interval 1 conflicts with intervals 2 and 5, so they are removed. The nert shortest is 3, which conflicts with interval 6, and the only remaining interval is 4." YOUR ANSWER HERE. We've provided you with some sample code to draw such a figure natively in LATEX, you just need to modify the start/end points and possibly add more intervals if you need as well as answer the rest of the question!). (b) Consider a greedy algorithm which always selects the longest appointment first. Draw an example with at least 5 appointments where this algorithm fails. Show the order in which the algorithm selects the intervals, and also show a larger subset of non-overlapping intervals than the subset output by the greedy algorithm. The same comments apply here as for 2a in terms of level of explanation