Consider a greedy strategy for the following problem We have a company with n wo

Question

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?

Explanation / Answer

Algorithms for optimization problems typically go through a sequence of steps, with a set of choices at each step.Greedy algorithms do not always yield optimal solutions, but for many problems they do.The greedy method is quite powerful and works well for a wide range of problems.

Activity selecttion problem:

Given: Set S = fa1; a2; : : : ; ang of n proposed activities that wish to use a resource that can serve only one activity at a time;
- ai has a start time si and a finish time fi, 0 si < fi < 1
- If ai is scheduled to use the resource, it occupies it during the interval [si; fi) ) can schedule both ai and aj iff si fj or sj fi (if this happens,
then we say that ai and aj are compatible)

A greedy algorithm obtains an optimal solution to a problem by making a sequence of choices. For each decision point in the algorithm, the choice that seems best at the moment is chosen.

Example : Consider the following 3 activities sorted by finish time.

     start[] = {10, 12, 20};

     finish[] = {20, 25, 30};

A person can perform at most two activities. The maximum set of activities that can be executed is {0, 2}

The greedy choice is to always pick the next activity whose finish time is least among the remaining activities and the start time is more than or equal to the finish time of previously selected activity. We can sort the activities according to their finishing time so that we always consider the next activity as minimum finishing time activity.

1) Sort the activities according to their finishing time
2) Select the first activity from the sorted array and print it.
3) Do following for remaining activities in the sorted array.a) If the start time of this activity is greater than or equal to the finish time of previously selected activity then select this activity and print it.

Instead of trying all activities wk, we simply chose the one with the earliest finish time of all those still compatible with the scheduled ones.
- This is a greedy choice in that it maximizes the amount of time left over to schedule other activities
- Let Sk = {ai belongs to S : si fk} be set of activities that start after ak finishes
- If we greedily choose a1 first (with earliest finish time), then S1 is the only subproblem to solve

Here for the problem given we take;

For every time instant Ti, we want a worker from the Committee present.

Let w1, w2...wn be the workers, sorted by their start times s_i. (Worker w1 starts the earliest shift, and worker wn starts the very last shift.)

Introduce a new Indicator variable (boolean):

Y_i = 1 if worker i is part of the committeee

Y_i = 0 otherwise.

It takes O(n log n) time if input activities may not be sorted. It takes O(n) time when it is given that input activities are always sorted.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.