## Dynamic-Programming Algorithm

## for the Activity-Selection Problem

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*^{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 [*s*_{j}, f_{j}) do not overlap,
that is, *i* and *
j *are compatible if
*s*_{i }≥
*f*_{j }
and *s*_{j }≥
*f*_{i
}

### Dynamic-Programming Algorithm

The finishing time are in a sorted array* **
f*[*i*] and the starting
times are in array *s*[*i*]. The array
*m*[*i*] will store
the value *m*_{i}, where
*m*_{i} is the size of the
largest of mutually compatible activities among activities {1, 2, . . . , i}.
Let BINARY-SEARCH(*f, s*) returns the index of a number
*i* in the
sorted array *f *
such that *f*(*i*) ≤ *s* ≤* f*[*i*
+ 1].

**for*** i* =1 **to**
*n*

**do ** *m*[*i*] = max(*m*[*i*-1], 1+
*m* [BINARY-SEARCH(*f,
s*[*i*])])

We have *P*(*i*] = 1 if activity *i* is in optimal selection,
and *P*[*i*] = 0

**otherwise**

* i* =
*n*

**while*** i* > 0

**do if** *m*[*i*] = *m*[*i*-1]

**then** *P*[*i*] = 0

* i* =
*i *- 1

**else**

* i* = BINARY-SEARCH (*f, s*[*i*])

* P*[*i*] = 1

**Analysis**

The running time of this algorithm is *
O(n lg n) *because
of the binary search which takes *lg(n)* time as opposed to the
*O(n)*
running time of the greedy algorithm. This greedy algorithm assumes that the
activities already sorted by increasing time.