Skip to content

Latest commit

 

History

History
34 lines (23 loc) · 1.44 KB

436.-find-right-interval.md

File metadata and controls

34 lines (23 loc) · 1.44 KB

436. Find Right Interval

  • Medium

  • You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique.

    The right interval for an interval i is an interval j such that startj >= endi and startj is minimized.

    Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

Analysis

It seems helpful if we have a sorted list of "start"s and do binary search in that to find the interval that we want. However, we also need the initial position of the starts. So, we are creating a 2d array that records [start, end, index].

Notice: Here the "bisect" function runs binary search and returns the index i for us to insert x into the array. The index i returned satisfy the following: for all items less then i, they are less then x. For those that are bigger than i, they are equal to or bigger than x.

{% embed url="https://docs.python.org/3/library/bisect.html" %}

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