G家店面

刚面完 八成挂了 狗家最近店面很偏爱interval的问题

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

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

刚开始没看懂题 做到后面卡住了

看来这个题也是用扫描线，建立std::map (key sorted)，从interval的起/终点 -> weight change. (i.e., entering interval, +weight; leaving interval, -weight). 然后扫描一遍map并且tracking intervals with max (accumulative) weight.

答应我一直刷题 发表于 2020-5-12 18:45
扫描线吧
用tuple list，每个区间起点(x1, +weight），终点(x2, -weight)，然后sort.
第一遍扫出max weight ...

他让我直接存到treemap里 然后找到最大的值 再做区间

请问下LZ多久约上的电面？ 給HR发了时间后一直没回复了... = =

slowdive 发表于 2020-5-12 16:57
请问下LZ多久约上的电面？ 給HR发了时间后一直没回复了... = =

很久 差不多一个月吧 而且我觉得店面比以前好像难了

这也太难了。。

Jackie.Wang 发表于 2020-5-13 06:21
很久 差不多一个月吧 而且我觉得店面比以前好像难了

一个月... 那岂不是我等到电面confirmation的时候 也基本要面了..... = =

zzgzzm 发表于 2020-5-12 17:22
看来这个题也是用扫描线，建立std::map (key sorted)，从interval的起/终点 -> weight change. (i.e., ente ...

nb 我经过提示才想到。。。

304671127 发表于 2020-5-12 17:34
这也太难了。。

我刚开始想了个O(n2)的 直接被否掉了

这太难了，对店面来说

扫描线吧
用tuple list，每个区间起点(x1, +weight），终点(x2, -weight)，然后sort.
第一遍扫出max weight，第二遍存下有max weight的区间。
空间复杂度O(n)，时间复杂度O(nlogn)