1. As a budding expert in algorithms, you decide that your semester service project will be to offer free technical interview prep sessions to your fellow students. Not surprisingly, you are immediately swamped with appointment requests at all different times from students applying many different companies, some with more rigorous interviews than others (i.e., some will need more help than others). Let A be the set of n appointment requests. Each appointment ai in A is a pair (starti, endi) of times and endi > starti. To manage all of these requests and to help the most student students that you can, you develop a greedy algorithm to help you manage which appointments you can keep and which ones you have to drop (you can only help one student at a time).

(a) (2points) Draw an example with at least 5 appointments where a greedy algorithm that selects the shortest appointment will fail.

(b) (2points) Draw an example with at least 5 appointments where a greedy algorithm that selects the longest appointment will fail.

(c) (6 points) Describe and prove correctness for a greedy algorithm that is guaranteed to choose the subset of appointments that will help the maximum number of students that you help.