Given n open intervals (a1, b1), (a2, b2), . . . , (an, bn) on the real line, each representing start and end times of some activity requiring the same resource, the task is to find the largest number of these intervals so that no two of them overlap.
Investigate the three greedy algorithms based on
a. earliest start first.
b. shortest duration first.
c. earliest finish first.
For each of the three algorithms, either prove that the algorithm always yields an optimal solution or give a counterexample showing this not to be the case.