狗狗vo

第二题为啥觉得整个tree去放insert record更好呢. insert就只需要插入就可以了, key就是time. 每次就是找ceiling.follow up如果数据量很大的话，其实可以用bucket先分，分成几个bucket, 然后bucket内部再做binary search.

不知道对不对...

给你点个赞！

第三题不应该是DP么。。还是说我理解的题意有问题？
用一个boolean array维护能不能跳到最后一个点，然后从后往前看,每次看第i个右侧的1/3/4号元素，只要有一个能跳，第i个就填true，不能填false。
举个栗子：input: 0 0 1 1 1 0 0 1 0
boolean array:    t  t  f f  f  t  t  f  t
举个栗子2:input: 0 0 1 1 1 1 0 1 0
boolean array:    f  f  f f  f  f  t  f  t
follow up也简单，把boolean array变成跳到最后所需的步数，不能跳填-1
当然dfs也能做，不过相当于没有剪枝，是不是时间复杂度起飞？

shirleykeat 发表于 2021-6-22 08:57
比如有一个list_a = [(0,0), (5,3), (7,1), (10, 0)] 意思是 在time = 0到4的时候 value是0 然后time在5 ...

你例子的答案是不是应该是：[(0, 0), (3, 2), (5, 5), (7, 3), (8, 1), (10, 0)]

如果是两个list，用two pointer可以吧？

shirleykeat 发表于 2021-6-22 08:57
比如有一个list_a = [(0,0), (5,3), (7,1), (10, 0)] 意思是 在time = 0到4的时候 value是0 然后time在5 ...

感觉这道题是priority queue, value是[圆柱末端, value] 然后算total?

shirleykeat 发表于 2021-6-21 20:50
是的 zszszszs

segment tree 难啊

不懂就问： 第一题能否考虑用treemap 存interval+ merge interval的方法而不用segment tree呢？对于每个x或者y， 用TreeMap存储所有的interval。overlap的interval merge了存在TreeMap里。在查边有没有被线段cover的时候，可以用TreeMap flloorKey找到现有线段，然后看这条边是否被现有线段完全覆盖。

"如果有billion级‍‌‍‌‍‌‌‌‌‌‌‌‍‍‌‌‍‌‌别的request 怎么处理"从method本身怎么考虑？

“如果有billion级‍‌‍‌‍‌‌‌‌‌‌‌‍‍‌‌‍‌‌别的request 怎么处理”

如果interval上下限不是很大的话，上一个hashmap。key是interval里每一个点，value是个boolean，代表这个点在不在interval里。

insert的时候，对interval里每一个值更新hashmap
读的时候，hashmap O(1) lookup

shirleykeat 发表于 2021-6-21 17:57
比如有一个list_a = [(0,0), (5,3), (7,1), (10, 0)] 意思是 在time = 0到4的时候 value是0 然后time在5 ...

正确结果是 [(0, 0), (3, 2), (5, 5), (7, 3), (8, 1), (10, 0)]
merge interval经典扫描线做法，TreeMap +height -height那种做法
第三题是jump game，背包问题，DP即可
另外第五题应该是 蠡口其药物