Consider a greedy strategy for the following problem We have a company with n workers. Worker w_i works a shift (s_i, f_i), where s_i is that worker's start time and f_i the finish time. We want to form a small committee C subset or equalto {w_1, ..., w_n} with the following property: for every worker w_i there exists a worker w_c Elementof C such that the shift of w_i overlaps with the shift of w_c. That is, the intervals (s_i, f_i) and (s_c, f_c) must intersect So the problem here is to find the smallest possible set C of workers whose shifts overlap with all workers (a) Describe the greedy choice. ("Choose the first worker with property P".) (b) Show that if there is an optimal solution for which the greedy choice was not made, then an exchange can be made to conform with your greedy choice ("Let schedule S use worker w_i who does not satisfy property P, and let w_k be the worker that does. Here I show that the schedule S', which is obtained by exchanging worker w_j for w_k, is just as good as S ...") (c) Describe, in English, how to implement a greedy algorithm. (d) How long would your algorithm take