Algorithm

Greedy-Iterative-Activity-Selector(A, s, f): 

    Sort A by finish times stored in f
    S = {A[1]} 
    k = 1
    
    n = A.length
    
    for i = 2 to n:
        if s[i] ≥ f[k]: 
            S = S U {A[i]}
            k = i
    
    return S

Proof of optimality

Let ${\displaystyle S=\{1,2,\ldots ,n\}}$ be the set of activities ordered by finish time. Assume that ${\displaystyle A\subseteq S}$ is an optimal solution, also ordered by finish time; and that the index of the first activity in A is ${\displaystyle k\neq 1}$, i.e., this optimal solution does not start with the greedy choice. We will show that ${\displaystyle B=(A\setminus \{k\})\cup \{1\}}$, which begins with the greedy choice (activity 1), is another optimal solution. Since ${\displaystyle f_{1}\leq f_{k}}$, and the activities in A are disjoint by definition, the activities in B are also disjoint. Since B has the same number of activities as A, that is, ${\displaystyle |A|=|B|}$, B is also optimal.

Once the greedy choice is made, the problem reduces to finding an optimal solution for the subproblem. If A is an optimal solution to the original problem S containing the greedy choice, then ${\displaystyle A^{\prime }=A\setminus \{1\}}$ is an optimal solution to the activity-selection problem ${\displaystyle S'=\{i\in S:s_{i}\geq f_{1}\}}$.

Why? If this were not the case, pick a solution B′ to S′ with more activities than A′ containing the greedy choice for S′. Then, adding 1 to B′ would yield a feasible solution B to S with more activities than A, contradicting the optimality.

Weighted activity selection problem

The generalized version of the activity selection problem involves selecting an optimal set of non-overlapping activities such that the total weight is maximized. Unlike the unweighted version, there is no greedy solution to the weighted activity selection problem. However, a dynamic programming solution can readily be formed using the following approach:^[1]

Consider an optimal solution containing activity k. We now have non-overlapping activities on the left and right of k. We can recursively find solutions for these two sets because of optimal sub-structure. As we don't know k, we can try each of the activities. This approach leads to an ${\displaystyle O(n^{3})}$ solution. This can be optimized further considering that for each set of activities in ${\displaystyle (i,j)}$, we can find the optimal solution if we had known the solution for ${\displaystyle (i,t)}$, where t is the last non-overlapping interval with j in ${\displaystyle (i,j)}$. This yields an ${\displaystyle O(n^{2})}$ solution. This can be further optimized considering the fact that we do not need to consider all ranges ${\displaystyle (i,j)}$ but instead just ${\displaystyle (1,j)}$. The following algorithm thus yields an ${\displaystyle O(n\log n)}$ solution:

Weighted-Activity-Selection(S):  // S = list of activities

    sort S by finish time
    opt[0] = 0  // opt[j] represents optimal solution (sum of weights of selected activities) for S[1,2..,j]
   
    for i = 1 to n:
        t = binary search to find activity with finish time <= start time for i
            // if there are more than one such activities, choose the one with last finish time
        opt[i] = MAX(opt[i-1], opt[t] + w(i))
        
    return opt[n]