# $O(n \log n)$ algorithm to find next interval that is also disjoint

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