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, Si and fi, finish time of an ith activity. Find the maximum size set of mutually compatible activities.

 

Compatible Activities

Activities i and j are compatible if the half-open internal [si, fi) and [sj, fj) do not overlap, that is, i and j are compatible if si fj  and sj ≥  fi

 

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 mi, where mi 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.