要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 1249|回复: 9
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
MCwong 发表于 2016-2-12 04:56:08 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

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

如果大家有什么比较好的思路和建议,希望可以共同讨论一下

上一篇:G家面经求指导
下一篇:最近有没有准备qumolo 电面的小伙伴,一起交流下!!
我的人缘0
helloc93 发表于 2016-2-12 05:05:09 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
同问~~很怕interval的题 有比较好的资料可以参考吗
回复 支持 反对

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
staycrazy 发表于 2016-2-12 07:47:49 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
一般来说,interval的题目如果不是特别难的,就是:
1. 按照end/start排序,然后greeeeeeeedy
2. 拆开end/start,纷纷变成event({event: start, time: xxx}),然后按照time排序,然后依次处理event

回复 支持 反对

使用道具 举报

我的人缘0
 楼主| MCwong 发表于 2016-2-12 13:16:44 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
staycrazy 发表于 2016-2-12 07:47
一般来说,interval的题目如果不是特别难的,就是:
1. 按照end/start排序,然后greeeeeeeedy
2. 拆开end ...

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

使用道具 举报

我的人缘0
staycrazy 发表于 2016-2-12 14:54:19 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
本帖最后由 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/

都是竞赛知识了。。。

回复 支持 反对

使用道具 举报

我的人缘0
samuelling 发表于 2016-2-12 15:19:00 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
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 来排序才能得到正确结果。所以觉得这类问题非常混乱,希望听到你的解答~
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
staycrazy 发表于 2016-2-13 02:21:05 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
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。
回复 支持 反对

使用道具 举报

我的人缘0
beer 发表于 2016-2-13 02:40:58 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
这是Merge Intervals吧?
我的思路是第一个作为prev,然后从第二个开始scan,依次用curr的start和prev的end比较,然后融合.
回复 支持 反对

使用道具 举报

我的人缘0
samuelling 发表于 2016-2-13 04:53:12 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
staycrazy 发表于 2016-2-12 10:21
按照start/end排序只影响你最后遍历时候的方向。两种办法没有本质区别,最后从前往后遍历或者从后往前遍 ...

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

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-27 18:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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