This is ridiculous, std::map::lower_bound is 50 times faster than the std::lower_bound on a sorted array.
Besides that, in so many other problems, the code written in plain C is running much faster than C++, it seems Leetcode doesn't compile the submitted code with any optimizing option.
My point is that, the problems on your website should lead people to learn programming in the correct direction, not misguiding them.
If I understand correctly, you put start value and index into a new array, sort them based on start value. And according to every end value, use binary search to search inside the new array for the least value that greater or equal to the end value.
Could you explain a little bit about the search method return statement?
return ends[lo].start>=intervals[start].end && ends[lo].idx != start?ends[lo].idx:-1;
Here is my code with the same idea, maybe slightly faster, but I don't know why
def findRightInterval(self, intervals):
:type intervals: List[Interval]
sorted_start = sorted((interval.start, index) for index, interval in enumerate(intervals))
sorted_end = sorted((interval.end, index) for index, interval in enumerate(intervals))
length = len(intervals)
result = [-1] * length
i = 0
for start in sorted_start:
while start >= sorted_end[i]:
result[sorted_end[i]] = start
i += 1