T(0)             T(1)            T(2)           T(3)           T(4)
   0  6  ∞  ∞     0  6  ∞  ∞     0  6  9  ∞      0  6  9 16    0  6  9 16
   2  0  3  ∞     2  0  3  ∞     2  0  3  ∞      2  0  3 10    2  0  3 10
  10  ∞  0  7    10 16  0  7    10 16  0  7     10 16  0  7   10 12  0  7
   ∞  5  ∞  0     ∞  5  ∞  0     7  5  8  0      7  5  8  0    7  5  8  0

c) The T⁽ⁱ⁾ matrices are given below. The solution is given in T⁽⁴⁾.

  T(0)              T(1)          T(2) = T(3) = T(4)
  1  1  0  0      1  1  0  0       1  1  0  0
  1  1  0  0      1  1  0  0       1  1  0  0
  1  0  1  1      1  1  1  1       1  1  1  1
  0  1  0  1      0  1  0  1       1  1  0  1

b) The time required after sorting is Θ(n), since it takes time O(1) to consider each item -- for each item we need only compare its starting time to the latest finish time so far, update the output set if necessary, and update the latest finish time if necessary -- and O(1) time to initialize the output set. Note that since we consider the items in order of finish time, updating the latest finish time means that whenever a new item is added to the output set we unconditionally update the latest finish time to this new item's finish time.

c) Let x be the activity under consideration. Call its start time s and its finish time f. First suppose that the algorithm chooses to include x. Then by the way the algorithm works, all activities that were included earlier must have finish time at least as early as s, so they cannot overlap x. Now suppose that the algorithm does not choose to include x. Then there must be some activity with finish time later than s. Since the activities are considered in order of finish time, this activity cannot finish after time f, so it cannot start after time f. Therefore this activity is incompatible with x.

d) Among all the optimal solutions that differ from A, let O be the one with the largest value of k (where k is defined as in part d). Then by part (d), there is another optimal solution that contains the first k items of A. If this solution is not equal to A, then we have contradicted the choice of O. So this optimal solution is equal to A, meaning that A is optimal.

EXTRA CREDIT: Let x be the kth item selected by the greedy algorithm. Call its start time s and its finish time f. By assumption x ε A-O. Let y be an activity in O that is incompatible with x. Since y is in O, it must be compatible with the first k-1 items selected by A, since these are also in O. So since the greedy algorithm selected x and not y, it must have considered x before y, so y finishes no earlier than time f. On the other hand, to be incompatible with x, it must start strictly before time f. Any two tasks in O that started before time f and finished no earlier than time f would be incompatible with each other, so since O is a solution, there must be at most one such task y. So the solution obtained from O by adding x and deleting any such y is optimal (since it has size at least as big as O), and it contains the first k activities selected by the greedy algorithm.

Although we don't need this for the proof, note that y must exist, since otherwise O would be smaller than A and therefore not optimal.

b) A[0] and A[1] will be empty, A[2] will be (19 22 35 44), and A[3] will be (3 13 23 33 43 53 63 73) as before.

c) In the worst case, no A[i] is empty and there will be merges into arrays of size 2, 4, ..., 2^k. This cost will dominate the Θ(k) cost of the rest of the algorithm, so the overall cost will be Θ(2^k+1), or Θ(n).

d) The merge of two arrays of size 2ⁱ into an array of size 2ⁱ⁺¹ will occur with probability 1/2ⁱ⁺¹ and cost Θ(2ⁱ⁺¹), so the total cost for a given value of i over all n insertions will be Θ((1/2ⁱ⁺¹) (2ⁱ⁺¹) n), or Θ(n). Since there are Θ(log n) possible array sizes, the total cost for all merges will be Θ(n log n). Since the total cost of the rest of the insertions (besides the merges) is O(log n), the total cost of all n insertions is Θ(n log n).

e) If n is a power of 2, then the amortized cost of the first n insertions is Θ(n log n)/n, or Θ(log n). This remains true if n is not a power of 2, since the numerator is Ω(2^k-1 log 2^k-1) and O(2^k log 2^k), and the denominator is Ω(2^k-1) and O(2^k-1 log 2^k). Finally, if the data structure is not initially empty, say with size m, we may choose n > m. In this case the previous analysis still holds, since since the probabilities in (d) of merging for arrays 0 through k remain the same, and there are still only Θ(log n) possible array sizes.