Complexity for interval scheduling #2
Description
The current complexity is O(n^2) because whenever we are looking for overlaps against a given task we check against all remaining tasks. By keeping track of the chronological order of when the tasks end, we can ensure we do not pick a task that ends later than it has to. This way we don't have to check all tasks for overlaps, but instead iterate until either there are no more tasks or the next task doesn't overlap (in which case we know to add it, since it's the task ending soonest that doesn't overlap). This reduces the runtime complexity to O(n logn) because of the required sorting steps.