Twitter 店面

pyemma 发表于 2015-11-1 12:23
感觉就是用DP吧，先把Array按照左端点sort一遍，然后从最后往前撸，dp存储以i开始的最长嵌套距离。时间复杂 ...

这个题要把序列找出来，所以我觉得用DP反倒不如用类似深搜的方式来解决更好，因为搜索的过程中可以不断地动态剪枝

楼主， 我决定Twitter现在有种不缺人的感觉，你这电面题比我当年那个可是要难不少。

这题我的idea是：1. 根据左端排序 2. 对排好的序列，建立一个size相等的vector结构， 找到每个interval的孩子序列，并且对孩子也记录父亲信息，然后合并这个序列（一个孩子可能同时也是另一个孩子的孩子） 3. 对处理后的这个vector每个没有父亲的元素进行DFS。

“ 让求其中最长的嵌套interval序列”是什么意思啊

jun2015 发表于 2015-11-1 12:10
嵌套深度最深

“嵌套深度最深”到底是什么意思啊，能不能再据个例子

这题idea是不是像toposort，比如[-101, 90], [1, 5], [-5, 10] id 为 1，2，3，4
然后 1－》3 表示 1 嵌套 3，1-》4 表示1嵌套4等
然后就找最长路径 1-》3-》4 或 2-》3－》4

tktrung 发表于 2015-11-3 09:21
这题idea是不是像toposort，比如[-101, 90], [1, 5], [-5, 10] id 为 1，2，3，4
然后 1－》3 表示 1 嵌套 ...

这道题我会像lintcode的Longest Increasing Continuous subsequence II那样解，可能还有更好办法，不过这个解法很直观。先是n^2的时间遍历构建一个map<int, set<int>>，其中key为1，value为一个set，表示id为1的interval包含了id为xx的interval，其中xx是value set的一个元素。然后，按照dp的办法更新一个array，array的每个元素就是从id为i的interval出发能够找到的最长subsequence。注意后面的寻找subsequenece的过程是O(N)的，原因和lintcode那道题一样。

tktrung 发表于 2015-11-3 09:21
这题idea是不是像toposort，比如[-101, 90], [1, 5], [-5, 10] id 为 1，2，3，4
然后 1－》3 表示 1 嵌套 ...

但是这样的话你要考虑建立嵌套的拓扑结构所需的复杂度