一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 828|回复: 9
收起左侧

[算法题] 两道interval相关的题求教

[复制链接] |试试Instant~ |关注本帖
MCwong 发表于 2016-2-12 04:56:08 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
lz最近刷面经的时候看到一道题:
Given a set of (start, end) pairs of timestamps where end > start, write an algorithm to return the smallest set of disjoint intervals containing every pair of (start, end) in the original set. 类似类似



类似这种区间重叠的题目感觉一直没有很好的思路,比如要用什么样的数据结构去保存这些区间以便之后的查询。


还有一道是square的面经题,也是类似的区间问题, 具体可以参考一下链接:

http://www.1point3acres.com/bbs/thread-143209-1-1.html

如果大家有什么比较好的思路和建议,希望可以共同讨论一下
helloc93 发表于 2016-2-12 05:05:09 | 显示全部楼层
同问~~很怕interval的题 有比较好的资料可以参考吗
回复 支持 反对

使用道具 举报

staycrazy 发表于 2016-2-12 07:47:49 | 显示全部楼层
一般来说,interval的题目如果不是特别难的,就是:
1. 按照end/start排序,然后greeeeeeeedy
2. 拆开end/start,纷纷变成event({event: start, time: xxx}),然后按照time排序,然后依次处理event

回复 支持 反对

使用道具 举报

 楼主| MCwong 发表于 2016-2-12 13:16:44 | 显示全部楼层
staycrazy 发表于 2016-2-12 07:47
一般来说,interval的题目如果不是特别难的,就是:
1. 按照end/start排序,然后greeeeeeeedy
2. 拆开end ...

同意,一些简单的区间操作可以排序+greedy, 然而如果是像第二题那种,需要维护重合部分的状态,greedy就不怎么行的通了, 那个帖子也有讨论用map来存状态的, 然而好像依然不是面试官满意的解
回复 支持 反对

使用道具 举报

staycrazy 发表于 2016-2-12 14:54:19 | 显示全部楼层
本帖最后由 staycrazy 于 2016-2-12 15:02 编辑
MCwong 发表于 2016-2-12 13:16
同意,一些简单的区间操作可以排序+greedy, 然而如果是像第二题那种,需要维护重合部分的状态,greedy就 ...

我当时没看第二题,第二题是类似RMQ,要求优update和query。每次query drop区间里最大的值,然后需要update这个区间到新的高度。

https://zh.wikipedia.org/wiki/%E ... C%E6%9F%A5%E8%AF%A2

https://www.topcoder.com/communi ... st-common-ancestor/

都是竞赛知识了。。。

回复 支持 反对

使用道具 举报

samuelling 发表于 2016-2-12 15:19:00 | 显示全部楼层
staycrazy 发表于 2016-2-11 15:47
一般来说,interval的题目如果不是特别难的,就是:
1. 按照end/start排序,然后greeeeeeeedy
2. 拆开end ...

请问一下怎么判断是根据start还是end排序呢?因为自己做leetcode的时候像meeting room 这类问题按照start和end分别排序都做了一遍,都是可以的。但是有的时候貌似只能按照start或者end,比如给你一个set of intervals,返回最多none overlapping intervals 的数量,这时候只能根据end 来排序才能得到正确结果。所以觉得这类问题非常混乱,希望听到你的解答~
回复 支持 反对

使用道具 举报

samuelling 发表于 2016-2-12 15:19:11 | 显示全部楼层
请问一下怎么判断是根据start还是end排序呢?因为自己做leetcode的时候像meeting room 这类问题按照start和end分别排序都做了一遍,都是可以的。但是有的时候貌似只能按照start或者end,比如给你一个set of intervals,返回最多none overlapping intervals 的数量,这时候只能根据end 来排序才能得到正确结果。所以觉得这类问题非常混乱,希望听到你的解答~
回复 支持 反对

使用道具 举报

staycrazy 发表于 2016-2-13 02:21:05 | 显示全部楼层
samuelling 发表于 2016-2-12 15:19
请问一下怎么判断是根据start还是end排序呢?因为自己做leetcode的时候像meeting room 这类问题按照start和 ...

按照start/end排序只影响你最后遍历时候的方向。两种办法没有本质区别,最后从前往后遍历或者从后往前遍历,总有一条走得通。

你说的non-overlapping,其实更加直观的解决方案是把所有start, end分开然后排序,一个count计数器,遇到start就count++,遇到end就count--,如果出现count == 1然后count--的情况,就是一个没有和任何其他interval overlap的interval。
回复 支持 反对

使用道具 举报

beer 发表于 2016-2-13 02:40:58 | 显示全部楼层
这是Merge Intervals吧?
我的思路是第一个作为prev,然后从第二个开始scan,依次用curr的start和prev的end比较,然后融合.
回复 支持 反对

使用道具 举报

samuelling 发表于 2016-2-13 04:53:12 | 显示全部楼层
staycrazy 发表于 2016-2-12 10:21
按照start/end排序只影响你最后遍历时候的方向。两种办法没有本质区别,最后从前往后遍历或者从后往前遍 ...

哦哦不过你说的后一种扫描线算法是只有在计算none overlapping的时候才用吗?平常merge/insert之类的就可以按照start/end 排序就可以了?感谢🙏
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 19:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表