[Leetcode] Binary search--436. Find Right Interval
Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the "right" of i.
For any interval i, you need to store the minimum interval j's index, which means that the interval j has the minimum start point to build the "right" relationship for interval i. If the interval j doesn't exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.
Note:
- You may assume the interval's end point is always bigger than its start point.
- You may assume none of these intervals have the same start point.
def binarySearchStartPoint(targetLst, ele):
if len(targetLst) == 1: #only one element
if targetLst[0][0].start >= ele:
return targetLst[0][1]
else:
return -1
l = 0
h = len(targetLst)-1
while (l <= h):
mid = (l + h)/2
if ele == targetLst[mid][0].start:
return targetLst[mid][1] #index
elif ele < targetLst[mid][0].start:
h = mid - 1
else:
l = mid + 1
#print ( 'ddd : ', len(targetLst), l)
if l >= len(targetLst):
return -1
return targetLst[l][1] intersIndexLst = [(intl, i) for i, intl in enumerate(intervals)] intersIndexSortedLst = sorted(intersIndexLst, key = lambda k: k[0].start)
i = 0
ansLst = [0] * len(intersIndexSortedLst) while (i < len(intersIndexSortedLst)-1):
endElement = intersIndexSortedLst[i][0].end
targetLst = intersIndexSortedLst[i+1:]
currInd = intersIndexSortedLst[i][1]
indRight = binarySearchStartPoint(targetLst, endElement)
#print ('targetLst: ', endElement, indRight)
ansLst[currInd] = indRight
i += 1
ansLst[intersIndexSortedLst[-1][1]] = -1 #the last emelement in intersIndexSortedLst
return ansLst
2.
I refer to other's solution, which makes the question so simple.
(1) only need to maintain the start point with a tuple
(2) bisect can be used in that way,
(3) after sorted, directly compare the end with the original interval list to find the insertion position (index)
ansLst = []
intersIndexLst = [(intl.start, i) for i, intl in enumerate(intervals)]
intersIndexSortedLst = sorted(intersIndexLst)
for intl in intervals:
ind = bisect_left(intersIndexSortedLst, (intl.end, ))
ansLst.append(intersIndexSortedLst[ind][1] if ind < len(intervals) else - 1)
return ansLst
--reference:
https://discuss.leetcode.com/topic/65596/python-o-nlogn-short-solution-with-explanation
最新文章
- Idea中包内中的置文件如何发布到编译后的目录中去
- NPOI操作excel
- 10月16日下午MySQL数据库CRUD操作(增加、删除、修改、查询)
- php文件上传参数设置
- 【笨嘴拙舌WINDOWS】BMP图片浏览器
- 转载:Linux内核探索之路——关于书
- Properties文件,Data,Calendar类的使用
- linux下svn客户端报错Cannot negotiate authentication mechanism的解决方法
- 【转】nginx之逻辑运算
- EasyMonkeyDevice vs MonkeyDevice&;amp;HierarchyViewer API Mapping Matrix
- 201521123081《Java程序设计》 第4周学习总结
- 前端请求参数MD5加密校验,参数串解密
- python 题库1
- 《.NET手札》
- rabbitmq安装与高可用集群配置
- Lync 2013安装中遇到的关于SQL Mirroring的一次报错的解决
- 使用 MD5 加密 去重对插入的影响
- eclipse 预览Android界面报错
- linux系统挂载U盘,中文文件名乱码解决方案
- Btrace的使用方法