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] 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) starts, idx = [x for x in intvl], [x 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
@dalwise I see. Thanks a lot!
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] < 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] < end: lo = lo+1 else: hi = mid if lo == len(intervals): result.append(-1) else: result.append(sorted_start[lo]) 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] < 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] < end: jLower = jMid
@gor.rennie Ah, I see. How fool I am~! I was mean to use binary search, but I mistook
mid. Thanks for point that out.
The correct snippet should be,
while lo < hi: mid = (lo + hi) // 2 if sorted_start[mid] < end: lo = mid+1 else: hi = mid
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.