Your final exams are over and you are catching up on watching sports on TV. You have a schedule of interesting matches coming up all over the world during the next week. You hate to start or stop watching a match midway, so your aim is to watch as many complete matches as possible during the week.
Suppose there are $n$ such matches scheduled during the coming week and you know the starting and finishing time for each match.
- Describe an efficient algorithm to compute the following: for each match, what is the next match whose starting time is strictly later than the finishing time of the current match? Analyze the worse-case complexity of your algorithm.