Python O(nlogn) short solution with explanation


  • 13

    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
    

  • 0
    W

    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
    

  • 1

    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.


  • 0
    W

    @dalwise I see. Thanks a lot!


  • 2
    W

    Python is just beautiful isn't it


  • 0

    This solution is concise and nice. Love it.


  • -1
    N

    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?


  • 0
    N

    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?


  • 1
    G

    @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
    

  • 0
    N

    @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
    

  • 0
    L
    This post is deleted!

Log in to reply
 

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