Say there are some intervals $\{1, \ldots ,n\}$ with starting times and ending times, and they're sorted in order of starting time from first to last in an array intervals$[]$. Now I want create an array next$[]$ such that next$[i]$ is the interval after interval $i$ whose starting time is as close to $i$'s ending time as possible. The notes I'm reading says it is possible to do this in $n \log n$, but I don't see how. The fastest algorithm I have come up with would iterate over intervals$[]$, and in each step "look ahead" until it finds a starting time after $i$'s ending time. The worst possible scenario would be when all the intervals are bunched together (none are disjoint), in which case you would have to iterate over all of $i + 1, i + 2, \ldots ,n$ at each step $i$. This would be $O(n^2)$ because the total number of checks would be $0 + 1 + \cdots + n-1$ since we make $n-1$ for first the first number, $n-2$ for the second, etc. Am I missing a way to cut it down to $O(n \log n)$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
For interval i, you can binary search end[i] among the sorted array begin[]. Each binary search takes log n time.
