leetcode_436

发表于   |   分类于

Find Right Interval

题目戳这

题意

给定一个含有interval的List数组，每个interval其实就是一个元组形式，左右区间，找到每个interval(x)的右interval(y)的下标，使得x.end <= y.start，y.start越小越好，最好等于x.end。最后返回这么一个下标数组。

解法

我们将每个interval的start和下标存储起来，记为res,按照start从小到大排序起来，然后将每个interval的end扔到res中去二分即可。我们这里主要介绍一个模块，叫做bisect。是一个二分模块，有这么几个主要的用法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import bisect
(1)查找
bisect.bisect_left(a,val, [,lo,[hi]])
在有序数组a中寻找应该插入val的位置，lo,hi是可选参数，为二分的区间，默认为整个数组。
返回一个整数，代表的是第一个小于val的数的下标值。
bisect.bisect_right(a,val, [,lo,[hi]]) 同理，返回的是第一个大于val的数的下标值。
(2)插入
bisect.insort_left(a,val) 在有序表中插入val，使得有序表仍然有序，
如果val已经存在，则在它的左边插入。
bisect.insort_right(a,val) 同理，如果val已经存在，则在它的右边插入。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e
class Solution(object):
    def findRightInterval(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[int]
        """
        res = sorted([(x.start,i) for i,x in enumerate(intervals)])
        
        ans = []
        
        import bisect
        
        for x in intervals:
            index = bisect.bisect_right(res, (x.end,))
            # 这里可以直接用index的原因是上面用了(x.end,)这个伪元组来查找元素，
            #如果在res中存在x.end这个值，那么因为res中还有i，所以(x.end,)
            #肯定是小于(x.end,i)这个值的，故刚好就返回(x.end)的那个下标值
            ans.append(res[index][1] if index < len(res) else -1)
        
        return ans