两道interval相关的题求教

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

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

一般来说，interval的题目如果不是特别难的，就是：
1. 按照end/start排序，然后greeeeeeeedy
2. 拆开end/start，纷纷变成event({event: start, time: xxx})，然后按照time排序，然后依次处理event

同问~~很怕interval的题 有比较好的资料可以参考吗

staycrazy 发表于 2016-2-12 07:47
一般来说，interval的题目如果不是特别难的，就是：
1. 按照end/start排序，然后greeeeeeeedy
2. 拆开end ...

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

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/

都是竞赛知识了。。。

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 来排序才能得到正确结果。所以觉得这类问题非常混乱，希望听到你的解答～

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

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。

这是Merge Intervals吧？
我的思路是第一个作为prev，然后从第二个开始scan，依次用curr的start和prev的end比较，然后融合.

staycrazy 发表于 2016-2-12 10:21
按照start/end排序只影响你最后遍历时候的方向。两种办法没有本质区别，最后从前往后遍历或者从后往前遍 ...

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