喂shi店面一轮挂经

上个星期面完的wish一轮店面，面试官是华人，态度很友好，上来先问了下最impressive的项目是什么，然后具体问了问一些细节，总共大概是十分钟左右，然后开始上题。一道题，在leetcode上没看到有原题，但是不是非常难，主要是题目不太好理解。。。题目大意是先给定一个integer，代表的是终点（起点都是0），然后给一个list，list里面的元素是数组（interval），每个interval有三个元素，start，end，cost，代表了这次行动的起点终点和开销，要你从list中找出一系列interval，他们能组成从起点到终点的一条路径，并且cost最少，输出最小cost。下面给一个example：

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这周收到了拒信，也不是很明白哪里做得不太好，可能是我代码写的比较慢吧（有点紧张，手抖hhh），导致最后剩的时间不多。。。总之希望大家都加油吧，这个秋招感觉面试很不好拿，希望有一天能转运吧lol。最后求加米，目前手里只有120米左右，看不了面经很难受啊哈哈哈！

利扣 漆巴漆

dfs搜索所有可能路径不就是暴力吗，应该是最蠢的解法了吧。这题就是个无向图求最短路而已。

不知道能不能用DP，如果input没有sort过的话，可以用heap sort一下input按起点升序然后终点升序sort然后用一个长度为终点值+1的array记录走到每一点的最小值。然后从queue里提取所有区间如果新的值更小就更新。不知道这样的思路能不能做出来，看起来时间复杂度是O(nlogn)可能比dfs好一些。自己也不确定这样能不能做，求指点🙏

这道题不就是graph求最短路径吗

langcazhe 发表于 2019-10-12 07:08
楼主说下timeline

九月中旬内推的，月底收到OA，做完之后大概两天左右约了下一周店面

nhqgoal 发表于 2019-10-12 06:35
dfs搜索所有可能路径不就是暴力吗，应该是最蠢的解法了吧。这题就是个无向图求最短路而已。

有道理，想了一下，好像有点像minimum spanning tree，可以用union find做，当时傻了哈哈，多谢指点

Queenaaababy 发表于 2019-10-12 20:13
这道题不就是graph求最短路径吗

嗯嗯，应该是的，有点最小生成树的意思，可以用union find做应该，感谢指点哈哈

这个应该就是图上的 greedy ： dijkstra alg？