# Python O(nlogn) short solution with explanation

• My solution from contest with minimal cleanup. For each end point search for the first start point that is equal or higher in a previously constructed ordered list of start points. If there is one then return its index. If not return -1:

``````def findRightInterval(self, intervals):
l = sorted((e.start, i) for i, e in enumerate(intervals))
res = []
for e in intervals:
r = bisect.bisect_left(l, (e.end,))
res.append(l[r][1] if r < len(l) else -1)
return res
``````

• Nice solution! My idea is the same as yours, but my code is more verbose. I did not know that bisect can be used in that way. I have a quick question: how does bisect work when you give it a tuple like in your code? Thank you!

``````def findRightInterval(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[int]
"""
intvl = sorted([(x.start, i) for i, x in enumerate(intervals)], key=lambda x: x[0])
starts, idx = [x[0] for x in intvl], [x[1] for x in intvl]
res = []
for x in intervals:
pos = bisect.bisect_left(starts, x.end)
if pos == len(starts):
res.append(-1)
else:
res.append(idx[pos])
return res
``````

• Hi @WKVictor, sequences are compared item by item. See here for more details. So you don't need to specify a key for the sorted function, because the default sort function is similar already.

• @dalwise I see. Thanks a lot!

• Python is just beautiful isn't it

• This solution is concise and nice. Love it.

• I have the same idea, but I didn't know that bisect can use like this. So I use the same code from bisect, and change it to compare the tuple with index, like this,

``````lo = 0
hi = len(intervals)
while lo < hi:
mid = (lo + hi) // 2
if sorted_start[mid][0] < end:
lo = lo+1
else:
hi = mid
``````

But it has TLE at 11/17 test cases.

My complete code is,

``````def findRightInterval(self, intervals):
sorted_start = [(interval.start, index) for (index, interval) in enumerate(intervals)]
sorted_start.sort()
result = []

for interval in intervals:
end = interval.end
lo = 0
hi = len(intervals)
while lo < hi:
mid = (lo + hi) // 2
if sorted_start[mid][0] < end:
lo = lo+1
else:
hi = mid
if lo == len(intervals):
result.append(-1)
else:
result.append(sorted_start[lo][1])

return result
``````

Does anyone know why this is much slower than using bisect.bisect_left, although they are almost the same?

• I tried the super long 11/17 test case, which has 11000 intervals. By using bisect.bisect_left, it takes about 0.11 seconds to run. On the other hand, the above code takes about 15 seconds to run.

Is it because the bisect module actually has an optimized C module version?

• @NoAnyLove "Does anyone know why this is much slower" - looks like your problem is in the line:

``````> if sorted_start[mid][0] < end:
> 	lo = lo+1
``````

Instead of halving the search interval by setting 'lo = mid' and solving in O(log_2(n)) time, you are crawling up in single increments in O(n) time! That's a big problem.

For comparison, in my code (for which I implemented my own bisection search, for practice) had the equivalent lines:

``````if sortedStartPairs[jMid][1] < end:
jLower = jMid
``````

• @gor.rennie Ah, I see. How fool I am~! I was mean to use binary search, but I mistook `lo` and `mid`. Thanks for point that out.

The correct snippet should be,

``````while lo < hi:
mid = (lo + hi) // 2
if sorted_start[mid][0] < end:
lo = mid+1
else:
hi = mid
``````

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.