0
$\begingroup$

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)$?

$\endgroup$
4
$\begingroup$

For interval i, you can binary search end[i] among the sorted array begin[]. Each binary search takes log n time.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.