第零章、必读系列
- 学习算法和刷题的框架思维
- 学习数据结构和算法读什么书
- 动态规划解题框架
- 动态规划答疑篇
- 回溯算法解题框架
- 为了学会二分查找,我写了首诗
- 滑动窗口解题框架
- 双指针技巧解题框架
- Linux 的进程、线程、文件描述符是什么
- Git / SQL / 正则表达式的在线练习平台
- 动态规划设计:最长递增子序列
第一章、动态规划系列
- 编辑距离
- 经典动态规划问题:高楼扔鸡蛋
- 经典动态规划问题:高楼扔鸡蛋(进阶)
- 动态规划之子序列问题解题模板
- 动态规划之博弈问题
- 贪心算法之区间调度问题
- 动态规划之KMP字符匹配算法
- 团灭 LeetCode 股票买卖问题
- 团灭 LeetCode 打家劫舍问题
- 动态规划之四键键盘
- 动态规划之正则表达
- 最长公共子序列
第二章、数据结构系列
第三章、算法思维系列
- 算法学习之路
- 回溯算法团灭排列、组合、子集问题
- twoSum 问题的核心思想
- 常用的位操作
- 拆解复杂问题:实现计算器
- 烧饼排序
- 前缀和技巧
- 字符串乘法
- FloodFill 算法详解及应用
- 区间调度之区间合并问题
- 区间调度之区间交集问题
- 信封嵌套问题
- 几个反直觉的概率问题
- 洗牌算法
- 递归详解
第四章、高频面试系列
- 如何高效寻找素数
- 如何运用二分查找算法
- 如何高效解决接雨水问题
- 如何去除有序数组的重复元素
- 如何寻找最长回文子串
- 如何 k 个一组反转链表
- 如何判定括号合法性
- 如何寻找消失的元素
- 如何寻找缺失和重复的元素
- 如何判断回文链表
- 如何在无限序列中随机抽取元素
- 如何调度考生的座位
- Union-Find 算法详解
- Union-Find 算法应用
- 一行代码就能解决的算法题
- 二分查找高效判定子序列
第五章、计算机技术
文章来源于网络收集而来,版权归原创者所有,如有侵权请及时联系!
区间调度之区间交集问题
本文是区间系列问题的第三篇,前两篇分别讲了区间的最大不相交子集和重叠区间的合并,今天再写一个算法,可以快速找出两组区间的交集。
先看下题目,LeetCode 第 986 题就是这个问题:
题目很好理解,就是让你找交集,注意区间都是闭区间。
思路
解决区间问题的思路一般是先排序,以便操作,不过题目说已经排好序了,那么可以用两个索引指针在 A
和 B
中游走,把交集找出来,代码大概是这样的:
# A, B 形如 [[0,2],[5,10]...]
def intervalIntersection(A, B):
i, j = 0, 0
res = []
while i < len(A) and j < len(B):
# ...
j += 1
i += 1
return res
不难,我们先老老实实分析一下各种情况。
首先,对于两个区间,我们用 [a1,a2]
和 [b1,b2]
表示在 A
和 B
中的两个区间,那么什么情况下这两个区间没有交集呢:
只有这两种情况,写成代码的条件判断就是这样:
if b2 < a1 or a2 < b1:
[a1,a2] 和 [b1,b2] 无交集
那么,什么情况下,两个区间存在交集呢?根据命题的否定,上面逻辑的否命题就是存在交集的条件:
# 不等号取反,or 也要变成 and
if b2 >= a1 and a2 >= b1:
[a1,a2] 和 [b1,b2] 存在交集
接下来,两个区间存在交集的情况有哪些呢?穷举出来:
这很简单吧,就这四种情况而已。那么接下来思考,这几种情况下,交集是否有什么共同点呢?
我们惊奇地发现,交集区间是有规律的!如果交集区间是 [c1,c2]
,那么 c1=max(a1,b1)
,c2=min(a2,b2)
!这一点就是寻找交集的核心,我们把代码更进一步:
while i < len(A) and j < len(B):
a1, a2 = A[i][0], A[i][1]
b1, b2 = B[j][0], B[j][1]
if b2 >= a1 and a2 >= b1:
res.append([max(a1, b1), min(a2, b2)])
# ...
最后一步,我们的指针 i
和 j
肯定要前进(递增)的,什么时候应该前进呢?
结合动画示例就很好理解了,是否前进,只取决于 a2
和 b2
的大小关系:
while i < len(A) and j < len(B):
# ...
if b2 < a2:
j += 1
else:
i += 1
代码
# A, B 形如 [[0,2],[5,10]...]
def intervalIntersection(A, B):
i, j = 0, 0 # 双指针
res = []
while i < len(A) and j < len(B):
a1, a2 = A[i][0], A[i][1]
b1, b2 = B[j][0], B[j][1]
# 两个区间存在交集
if b2 >= a1 and a2 >= b1:
# 计算出交集,加入 res
res.append([max(a1, b1), min(a2, b2)])
# 指针前进
if b2 < a2: j += 1
else: i += 1
return res
总结一下,区间类问题看起来都比较复杂,情况很多难以处理,但实际上通过观察各种不同情况之间的共性可以发现规律,用简洁的代码就能处理。
另外,区间问题没啥特别厉害的奇技淫巧,其操作也朴实无华,但其应用却十分广泛,接之前的几篇文章:
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论