911 views
1 votes
1 votes

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.

  1. 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.

2 Answers

Related questions

7 votes
7 votes
1 answer
3
go_editor asked May 23, 2016
911 views
You are given two sorted lists of integers of size $m$ and $n$. Describe a divide and conquer algorithm for computing the $k$-th smallest element in the union of the two ...
2 votes
2 votes
1 answer
4
go_editor asked May 27, 2016
417 views
Let $A$ be an array of $n$ integers, sorted so that $A \leq A \leq \dots \leq A[n]$. You are given a number $x$x. The aim is to find out if there are indices $k$ and $l...