Final answer:
Choosing intervals that maximize the number of points covered does not always work. The greedy algorithm has a complexity of O(n log n) and selects intervals that cover the maximum number of points at each step. The algorithm is proven to be optimal through a contradiction argument.
Step-by-step explanation:
(a) Counterexample:
Let's say we have the set of points {1, 3, 4, 6, 8}. If we choose the intervals [{1,4},{6,8}], which covers points 1, 3, 4, 6, and 8, we would think this is the maximum coverage. However, a better choice would be the intervals [{1,3},{4,6},{6,8}], which cover all the points in the set. So, choosing intervals that maximize the number of points covered does not always work.
(b) Pseudocode for greedy algorithm:
Sort the set of points in ascending order
Initialize an empty list of intervals
Iterate through the sorted points
If there is no interval or if the current point is greater than the end of the last interval
Create a new interval starting at the current pointAdd the interval to the listElse if the current point is within the range of the last intervalUpdate the end of the last interval to be the current point
The complexity of this greedy algorithm is O(n log n) as it involves sorting the set of points before iterating through them.
(c) Proof of optimality:
The greedy algorithm is optimal because it always chooses the interval that covers the maximum number of points at each step. Always selecting the interval with the earliest endpoint, ensures that no other valid interval can cover more points. This can be proven through a contradiction argument.