8. Recall that the optimal greedy algorithm for Interval Partitioning first sorts the intervals by their starting times. This question investigates what happens if we do not sort them in this order. (a) Give an example where the algorithm would return a non-optimal schedule if it did not sort the intervals. (b) Explain where the proof of correctness of the algorithm breaks down if the algorithm does not sort the intervals. 9. Let's consider a long, straight, quiet country road with houses scattered very sparsely along it. (We can picture the road as a long line segment, with an eastern endpoint and a western endpoint.) Further, let's suppose that the residents of all these houses are avid cell phone users. You want to place cell phone base stations at certain points along the road so that every house is within ten kilometers of one of the base stations. Give an efficient algorithm that achieves this goal, using as few base stations as possible. You do not have to prove that your algorithm is correct (but you are welcome to do so if you would like to). 10. Implement the optimal greedy algorithm for the interval scheduling problem in your chosen programming language. You may choose to read the input from either the keyboard or a file. If you want to test your program with large input, you may want to read from a file, however. Alternatively, you can read from the keyboard and then use input redirection (See, for example, https://chortle.ccsu.edu/java5/Notes/chap22/ ch22_2.html). Submit your code and the outputs of your code on a few sample inputs