An
activity-selection is the problem of scheduling a resource among several
competing activity.

**Problem Statement**

Given a set *S* of *n* activities with and start time, *S*_{i
}and *f _{i}*, finish time of an i

**Compatible Activities**

Activities

iandjare compatible if the half-open internal [s) and [_{i}, f_{i}s)_{j}, f_{j}

do not overlap, that is,iandjare compatible ifs≥_{i }f_{j }ands_{j }≥f_{i }

## Greedy Algorithm for Selection Problem

I. Sort the input activities by increasing finishing time.

f≤_{1}f≤ . . . ≤_{2}f_{n }II. Call

GREEDY-ACTIVITY-SELECTOR(s, f)

n= length [s]A={i}j= 1fori= 2tondo ifs≥_{i}f_{j}thenA= AU{i}j=ireturnset A

**Operation of the algorithm**

Let 11 activities are given *S* = {*p, q, r, s, t, u, v, w, x, y, z*}
start and finished times for proposed activities are (1, 4), (3, 5), (0, 6), 5,
7), (3, 8), 5, 9), (6, 10), (8, 11), (8, 12), (2, 13) and (12, 14).

A = {p} Initialization at line 2

A = {p, s} line 6 - 1^{st}iteration of FOR - loop

A = {p, s, w} line 6 -2^{nd}iteration of FOR - loop

A = {p, s, w, z} line 6 - 3^{rd}iteration of FOR-loop

Out of the FOR-loop and Return A = {p, s, w, z}

**Analysis**

Part I requires O

(n lg n)time (use merge of heap sort).

Part II requires θ(n)time assuming that activities were already sorted in part I by their finish time.

**Correctness**

Note that Greedy algorithm do not always produce optimal solutions but GREEDY-ACTIVITY-SELECTOR does.

**Theorem ** *
Algorithm GREED-ACTIVITY-SELECTOR produces
solution of maximum size for the activity-selection problem.*

Proof IdeaShow the activity problem satisfied

- Greedy choice property.
- Optimal substructure property.

**Proof**

- Let
*S = {1, 2, . . . , n}*be the set of activities. Since activities are in order by finish time. It implies that activity 1 has the earliest finish time.

Suppose,*AS*is an optimal solution and let activities in*A*are ordered by finish time. Suppose, the first activity in*A*is*k*.

If*k = 1*, then A begins with greedy choice and we are done (or to be very precise, there is nothing to proof here).

If*k 1*, we want to show that there is another solution*B*that begins with greedy choice, activity 1.

Let*B = A*- {*k*}{1}. Because*f*_{1 }*f*, the activities in_{k}*B*are disjoint and since B has same number of activities as*A*, i.e.,*|**A| = |B|*,*B*is also optimal. - Once the greedy choice is made, the problem reduces to finding an
optimal solution for the problem. If
*A*is an optimal solution to the original problem*S*, then*A` = A - {1}*is an optimal solution to the activity-selection problem*S` = {i S: S*._{i }f_{i}}

why? Because if we could find a solution*B`*to*S`*with more activities then*A`*, adding 1 to*B`*would yield a solution*B*to*S*with more activities than A, there by contradicting the optimality. □

As an example consider the example.** **Given a set of activities to among lecture halls. Schedule
all the activities using minimal lecture halls.

In order to determine which activity should use which lecture hall, the
algorithm uses the GREEDY-ACTIVITY-SELECTOR to calculate the activities in the
first lecture hall. If there are some activities yet to be scheduled, a new
lecture hall is selected and GREEDY-ACTIVITY-SELECTOR is called again. This
continues until all activities have been scheduled.

LECTURE-HALL-ASSIGNMENT (s, f)

n= length [s)

fori= 1 ton

do HALL [i] = NILk= 1

while (Not empty (s))

do HALL [k] = GREEDY-ACTIVITY-SELECTOR (s, t, n)

k=k+ 1

return HALL

*Following changes can be made in the GREEDY-ACTIVITY-SELECTOR (s, f) (see
CLR).*

j= first (s)

A=i

fori=j+ 1 ton

do ifs(i)not= "-"

then ifGREED-ACTIVITY-SELECTOR (

s, f, n)

j= first (s)

A=i=j + 1ton

ifs(i]not = "-" then

ifs[i] ≥f[j]|

thenA=AU{i}

s[i] = "-"

j=i

returnA

**Correctness**

The algorithm can be shown to be correct and
optimal. As a contradiction, assume the number of lecture halls are not optimal,
that is, the algorithm allocates more hall than necessary. Therefore, there
exists a set of activities *B* which have been wrongly allocated. An
activity b belonging to *B* which has been allocated to hall
*H*[*i*]
should have optimally been allocated to *H*[*k*]. This implies that
the activities for lecture hall *H*[*k*] have not been allocated
optimally, as the GREED-ACTIVITY-SELECTOR produces the optimal set of activities
for a particular lecture hall.

**Analysis**

In the worst case, the number of lecture halls require is
n. GREED-ACTIVITY-SELECTOR runs in *θ(n)*. The running time of this
algorithm is O(*n*^{2}).

**Two important Observations**

- Choosing the activity of least duration will not always produce
an optimal solution. For example, we have a set of activities {(3, 5), (6, 8),
(1, 4), (4, 7), (7, 10)}. Here, either (3, 5) or (6, 8) will be picked first,
which will be picked first, which will prevent the optimal solution of {(1, 4),
(4, 7), (7, 10)} from being found.

- Choosing the activity with the least overlap will not always produce solution. For example, we have a set of activities {(0, 4), (4, 6), (6, 10), (0, 1), (1, 5), (5, 9), (9, 10), (0, 3), (0, 2), (7, 10), (8, 10)}. Here the one with the least overlap with other activities is (4, 6), so it will be picked first. But that would prevent the optimal solution of {(0, 1), (1, 5), (5, 9), (9, 10)} from being found.

Dynamic-Programming Algorithm for the Activity-Selection Problem