[8 marks] The Story: In ancient times, there were hundreds of city states in Greece. Sometimes these city states banded together to fight other countries, but in other times, they often fought each other over borders. Among them, Sparta and Messenia shared a long border, and they fought multiple wars against each other. Suppose, after one of these wars, the kings of Sparta (Sparta was a oligarchy, so I used the plural form of king) decided to build a set of watchtowers to guard the borderline. Each watchtower would be responsible for watching over a section of the borderline. The Spartan military thus surveyed the borderline and identified a set of possible locations. Each location can be used to construct one watchtower. For each possible location, they also determined the (continuous) section of the borderline that could be guarded by the watchtower built on this location. They verified that, if they built a watchtower at each location, it would be sufficient to cover the entire borderline. However, since the sections guarded by some of these watchtowers would overlap with each other, it was possible to select a subset of these locations to construct enough watchtowers to guard the entire borderline. To save costs, it would be ideal to build as few watchtowers as possible, while still guarding the entire borderline. The Model: Mathematically, this borderline could be viewed as a simple curve; a simple curve is a curve that does not cross itself. Let A and B be the two endpoints of this curve, and let m be its length in Greek feet (Greek foot is called pous, and 1 Greek foot is equivalent to 0.308 meters). Furthermore, we identify each point in this curve by the length of the subcurve between this point and the endpoint A. Thus, the section of the borderline that could be guarded by a watchtower is represented by a closed interval [s, f]; this means that this watcher tower could guard the section for the borderline between and including points S and F, where the length of the section of the borderline between S and A is s Greek feet, the length of the section of the borderline between F and A is f Greek feet, and s < f. Then the length of the section of the borderline guarded by this watchtower is f s, which is also the length of the interval. Thus, the input to this problem is a set, I, of n intervals, and each interval in I represents the section of the borderline that can be guarded by the watchtower at a certain location. The union of all intervals in I is [0..m]. The output is a subset, I , of I, of minimum cardinality such that the entire borderline is guarded by the watchtowers corresponding to the selected intervals in I . Your first task: Suppose that, the Spartan kings hired you, a time traveler who happened to be in Ancient Greece at that time, to solve this problem. They also forwarded you one solution proposed by the Spartan Military: First select the location that could guard the section of the borderline of the longest length, and build a watchtower at this location. Then, among all remaining locations where watchtowers could still guard some of the unguarded portions of the borderline, select the location whose corresponding interval in I is the largest. Repeat this process. For example, if m = 13, and I = {[3, 10], [7, 13], [6, 11], [0, 4]}, then their strategy would first choose [3, 10], then [7, 13] and finally [0, 4]. Your first task is to show that this strategy does not always give an optimal solution by constructing a counterexample. Explain why the solution is not optimal.