https://leetcode.com/problems/find-right-interval

Let us look carefully at our statement: for each interval i we need to find interval j, whose start is bigger or equal to the end point of interval i. We can rephrase this: Given end of interval i, we need to find such point among starts of interval, which goes immedietly after this end of iterval i. How we can find this point? We can sort our intervals by starts (and hopefully there is no equal starts by statement) and then for each end of interval find desired place. Let us go through exapmle: [1,12], [2,9], [3,10], [13,14], [15,16], [16,17] (I already sorted it by starts):

  1. Look for number 12 in begs = [1,2,3,13,15,16]. What place we need? It is 3, because 12 <13 and 12 > 3.
  2. Look for number 9, again place is 3.
  3. Look for number 10, place is 3.
  4. Look for number 14, place is 4, because 13<14<15.
  5. Look for number 16, what is place? In is 5, because begs[5] = 16. Exactly for this reason we use bisect_left, which will deal with these cases.
  6. Look for number 17, what is place? it is 6, but it means it is bigger than any number in our begs, so we should return -1.

So, what we do:

  1. Sort our intervals by starts, but also we need to keep they original numbers, so I sort triplets: [start, end, index].
  2. Create array of starts, which I call begs.
  3. Creaty out result, which filled with -1.
  4. Iterate over ints and for every end j, use bisect_left. Check that found index t < len(begs) and if it is, update out[k] = ints[t][2]. Why we update in this way, because our intervals in sorter list have different order, so we need to obtain original index.

Complexity: time complexity is O(n log n): both for sort and for n binary searches. Space complexity is O(n).

class Solution:
    def findRightInterval(self, intervals):
        ints = sorted([[j,k,i] for i,[j,k] in enumerate(intervals)])
        begs = [i for i,_,_ in ints]
        out = [-1]*len(begs)
        for i,j,k in ints:
            t = bisect.bisect_left(begs, j)
            if t < len(begs):
                out[k] = ints[t][2]
        
        return out

If you like the solution, you can upvote it on leetcode discussion section: Problem 0436