snap 店面面经 onsite求经验

求大佬指点 下O(nlgn) 思路

knightna 发表于 2022-2-18 22:54
这道题和天空中的飞机那道题一样把

把任务时间点转换为 event (time, project_id, start/end), 然后time ...

你这个求的难道不是同时进行的task最多有多少个？

感觉有点像 利口 思撒五 或者 依儿伞五

也有点像伊叁捂伞

感觉是meeting room，然后相邻id相同就跳下一个

匿名者 发表于 2022-2-18 09:20
scan组 地里有另一个帖子说现在店面就会加这个 思路可以的

这个思路的dp部分，是一个二维dp吧，两个维度分别是end time和proj id，那这样的话状态数是n，每个状态都要搜索一遍task list，所以我理解整体的复杂度还是O(n^2)?

tasks cannot overlap right?
比如[(1, 1, 3), (2, 1, 4), (3, 4, 5)] - 员工只能做(1, 1, 3) 和 (3, 4, 5)么？
感觉像是以尔伞吴和涂房子的结合。

请问如何做到NLOGN呢？
这道题更像是一个背包问题？每个任务可以做 也可以不做
做的话，还得考虑到上一个任务是不是和当前任务属于一个PROJECT。
所以说每个状态有两个独立变量，上一个任务属于的PROJECT的编号 和当前任务的INDEX，所以时间复杂度是类似于N2
NLGN是怎么做到的呢？