To implement the greedy algorithm in Java to solve the activity selection problem, as described previously.

A possible implementation of the algorithm described to solve the activity selection problem is as follows:

Collections.sort(sortedActivities, (o1, o2) -> Integer.signum(o1.finish - o2.finish));
if (sortedActivities.size() > 0)
  selected.add(sortedActivities.get(0));
for (int i = 1; i < sortedActivities.size(); i++)
  if (sortedActivities.get(i).start >= selected.get(selected.size() - 1).finish)
    selected.add(sortedActivities.get(i));

After having sorted the activities by finish time, the selection part of the algorithm runs in O(n) time. Since we can't sort in O(n), the overall complexity of this algorithm is bounded by the complexity of the sorting algorithm. As seen in previous chapters, we can sort in O(nlog(n)) so that's the runtime complexity of the algorithm we've devised for the activity selection problem. The algorithm looks good, but how can we be sure that it always arrives at the optimal solution?