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)
FOR i = 1 to n
        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
FOR i = j + 1 to n
    DO IF s(i) not= "-"
            THEN IF

GREED-ACTIVITY-SELECTOR (s,f,n)
j = first (s)
A = i = j + 1 to n
        IF s(i] not = "-" THEN
            IF s[i] >= f[j]|           
                THEN A = A U {i}
                            s[i] = "-"
                                j = i
return A

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(n2).

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.