Interval相关的题目

题目列表

• meeting room I & II
• Skyline
• airline
• merge interval, insert interval

面经题

1.

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.

2.

是写一个function, drop(double position, double size), 即从高处掉一个方块， 左边的x坐标是position，方块的边长是size。然后它会一个个叠起来。 比如drop(1,4), drop(3,3)的话就会变成这样：

   bbb
   bbb
   bbb
aaaa
aaaa
aaaa. 
aaaa

然后它掉一大堆方块下来之后任何时候想要call一个叫getHeight()的function的话，你就得返回这堆方块里地最高点 （但getHeight在面试中没有写，面试官只叫我写了drop）

我就用map做了，做完后面试官说可以用tree，这样可以更加efficient。 就map<double, double>。跟Skyline有点像，就是记录高度变化的节点们~

类似skyline的做法，变成[start, end, height]

segment tree!

这道题做法

这个题是比较典型的线段树（segment tree）。一种解法是：

1. define Node { double x1, x2, h }，即代表X轴上坐标x1到x2之间能够遇到的最大高度为h
2. 每次来一个方块，设x坐标范围为(a, b)，高度ht, 那么查找segment tree，得到(a, b)之间最大高度，设为H，则（a，b）区间的新高度需要变成（H+ht）
3. 更新segment tree，使（a, b）区间新高度为（H+ht）：从根节点开始遍历， 1）如果cur_node的（x1，x2）完全包括了（a，b)

      1) cur_node.h = (H+ht)-google 1point3acres
      2) 如果cur_node有子节点, 递归更新子节点
   

   2) 如果(x1, x2)跟（a，b）部分重合，假设 a < x1 < b < x2: .

       1）生成一个新节点，范围：（a，x2）
       2）新节点left_child生成新节点, 范围(a，x1），right_child = cur_node (范围为x1-x2)
       3) 递归更新cur_node, 但范围从开始的（a，b）变成了（x1，b).
   

解题方法

一般来说，interval的题目如果不是特别难的，就是：

1. 按照 start/end 排序， 然后greedy

按照start/end排序只影响后面遍历时候的方向，没有本质区别。

1. 拆开 end/start, 又变成event, 然后按照time排序，依次处理event（线扫描法）

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

Solution

Reference

• 帖子