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.