1241. Find Right Interval

性能排名, 倒数第一. 哈哈.

idea:
用一个数组 xs 维护所有区间的起始点(interval.start),  排序.
对于一个区间, 然后在 xs 里面二分查找第一个大于等于 该区间右边界(interval.end).

数据结构:
xs: array, el = (itv, id), id 记录原始的索引.
或者,
xs: array, el = (start, end, id), 在 xs 里面找大于等于 interval.end 的第一个 id,


class Solution:
    """
    @param intervals: a list of intervals
    @return: return a list of integers
    1,5; 2,3; 3,4; 5;6
    """
    def findRightInterval(self, intervals):
        # write your code here
        def lt(this, other):
            if this.start < other.start:
                return True
            if this.start == other.start and this.end <= other.end:
                return True
            return False

        Interval.__lt__ = lt
        xs = []
        for i, itv in enumerate(intervals):
            xs.append((itv, i))
        xs.sort()
        n = len(xs)
        res = []
        for i in range(n):
            itv_end = xs[i][0].end
            right_i = self.bi_left(xs, i, itv_end)
            if right_i == -1:
                res.append((xs[i][1], -1))
                continue
            res.append((xs[i][1], xs[right_i][1]))
        res.sort()
        return [v[1] for v in res]

    def bi_left(self, xs, i, itv_end):
        n = len(xs)
        start, end = i, n
        while start < end:
            mid = (start + end)//2
            if xs[mid][0].start < itv_end:
                start = mid + 1
            else:
                end = mid
        # print(start, end)
        if start == n:
            return -1
        return start