### The Skyline Problem
要点：这题是难题，但是是重点难题，因为google常考，而且很多变形。题本身的pattern就是从左到右更新区间内存在值的最大值（对于这题就是skyline）。最简单的解法就是从左到右根据每个区间的enter/exit point更新存在值的集合。 同时因为区间值集合是不断变化的，需要有个data structure来track当前最大值，priority queue和tree map都可以。
实现上还有不少细节

- priority queue中元素类型？一个integer就够了
- compare function：等于？
    - 注意这个compare function是对时间点sort时候用的，而不是priority queue的，priority queue只根据height来排序
- 输入输出

EDIT: 补充更好的方法（更简单，并且beat 98.2% python)

- 因为building已经按start排好了，不用再排序。heap的最大height就是当前iteration的skyline。当然可能当前的height和当前skyline相同，不更新，这个code的结构就非常简单。
- 如何定义当前iteration？每个新的start和当前在heap的最大height的end做比较，两个分支：
    - 新的start的存在并且<=heap顶的end，这时候push（push要在loop里把所有==start的都push进去，==heap顶end也要push）
    - 1的reverse：没新start了，或者新start有空隙。这时候当前iteration就是考虑当前skyline的end（也就会上轮heap的最大值）。pop也是在loop里，把所有已经结束的段pop出来。
    - x: either next start or current end, so it’s in skyline
- 综上，总循环就是i<n or heap有值
- 边界条件：
    - 如果start和heap顶end相同，那么push，因为这样height是连续下去的
    - push的时候，多个start相同，要全部push，因为以最大的height为准
    - pop的时候要pop所有dead end：所以第二维也要按最大排序，这样height相同的时候保证end大的作为标准
- lintcode的输出方式：
    - 不是只需要跳变，而是需要输出非0区间
    - 区间：记录last height，而height变化的时候就输出，只要不是变成0，上一个end和下一个start是同一点，一起更新
    - 非0：如果是0，那么start是不更新的，reset为-1。同理，如果start是-1，下一次跳变更新start

### Meeting Rooms I/II
要点：这题和skyline类似，利用了interval start有序的特点，从左向右处理，用一个heap来动态表示当前占用rooms的时间段，所以heap的size就是room数。具体来说，

- heap是end time的min heap
- 当前？就是和新interval同时使用room的情况
- 如果min end<=新的interval.start，那么同一房间可以被这个interval重用。同时所有heap中end小的都要pop
- 如果min end>新的interval.start<min end：因为新interval.start比所有当前在heap中start的都晚，所以一定与所有heap中interval在某一点都有交集。所有max需要新房间，要push heap
- 所以在heap中的intervals必然都是在某一点互相重叠的
- 当然用endPoint sort + count的方法也可以。都是O(nlgn)，但不需要heap

https://repl.it/CfU6/4 (II)
错误点：不管是否pop，都要push新的：either 占新room or replace旧room
https://repl.it/CoP7 (I)

EDIT:
还有一类类似的题，是room (or 资源)有限，如何选最多的meeting。

4/15/16 Fri
### Wildcard Matching
要点：

- 基本code pattern是以待匹配string s为中心loop，一旦没有任何p的分支match，返回false。如果所有s匹配了，还要检查是不是p也exhausted，一种分支是剩下的p是’*’，这样也可以匹配。
- worst case: s: abcd, p: *e*f*g*h? every *, it swallows all abcd. so it O(n^2)

错误点：

- star和ss：star对应的是’*’这点在pattern中的位置，ss对应的是在上次没有swallow的s点的位置。实际上是记录了可以restore的状态

4/6/16
### Regular Expression Matching及变形
要点
fb的常考题, uber也考过。

思路: recursion是基本的结构: 假设s为待匹配string, p为pattern. 当前要匹配si和pi位置的char. 因为有*的存在, 自然分成两种case: 就是有*和没有*.  如果不是*, 只比较当前2个字符. 如果遇到*, 需要loop si当前位置所有向右(recursion)或者向左(dp)的相同char. 每一个会产生一个新的递归分支. 注意skip当前字符也是一个分支.

recursion:
base condition: 因为递归是向右, 所以如果pi超过pattern, 递归结束.
因为*是和左边的字符关联的, 递归向右的情况, 其条件是p[pi+1]=='*'.
worst case: s: aa…aab, p: a*…a*: 每一层都要loop所有s中的a，loop中的每一个进入一个同样loop的层，形成一个tree structure，所以是O(2^n)，space是O(n)

dp:
base condition: p向右移动
以当前字符是否为*作为条件