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

**Statement:** *Given a set S of n activities with and start time, S*_{i }
*and f _{i}, finish time of an i^{th} activity. Find the maximum size
set of mutually compatible activities.*

**Compatible Activities**

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

I. Sort the input activities by increasing finishing time.

*f _{1}* ≤

II Call GREEDY-ACTIVITY-SELECTOR (Sif)

*n*= length [*s*]*A*={*i*}*j*= 1- FOR
*i*= 2 to n - do if
*s*≥_{i}*f*_{j} - then A= AU{
*i*} -
*j*=*i* - Return
*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 ReturnA= {p, s, w, z}

**Analysis**

Part I requires *O(nlgn)* time (use merge of heap sort).

Part II requires *Theta(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 Idea: **Show the activity problem satisfied

I. Greedy choice property.

II. Optimal substructure property

**Proof:**

I. 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, *A is a subset of S* 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 not=1*, we want to show that there is another solution *B* that begins with
greedy choice, activity 1.

Let *B = A - {k} U {1}*. Because *f*_{1 }=< *f _{k}*, the
activities in

II. 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 in S: S _{i }>= f_{i}}*.

why?

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.

Dynamic-Programming Algorithm for the Activity-Selection Problem

**Problem: **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] = NIL

k= 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) (CLR).

j= first (s)

A=i

FORi=j+ 1 ton

DO IFs(i)not= "-"

THEN IF

**GREED-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}).

Observe that 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.

Also observe that 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.