uber的一道电面题，求讨论

vae371 · 2017-10-31 07:22:55

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

给一堆interval，比如{3,6},{2

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

只返回{2,4}

cx101220012 · 2017-11-13 09:03:45

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

jiayi411 · 2017-10-31 10:14:18

直接比是O(n)，排序是O(nlgn)

Corey_Lancer · 2017-10-31 07:26:43

复杂度什么要求。。？还是有比check 每个interval更快方法么。。

vae371 · 2017-10-31 07:30:04

Corey_Lancer 发表于 2017-10-31 07:26
复杂度什么要求。。？还是有比check 每个interval更快方法么。。

预处理一下，应该是有机会到O(1)的吧，不然就遍历一下太简单了。。。

yaya330 · 2017-10-31 08:18:40

同求预处理方法，我遇到的是给一堆interval，再给一堆数，算每个interval包含了哪些数

ld_xixi · 2017-10-31 08:25:21

interval排个序，然后跟二分跟start比？

ld_xixi · 2017-10-31 08:26:12

vae371 发表于 2017-10-31 07:30
预处理一下，应该是有机会到O(1)的吧，不然就遍历一下太简单了。。。

怎么做到O(1)？

littlegrass · 2017-10-31 08:34:32

请问楼主是什么时候内推的？

velinforever · 2017-10-31 08:41:08

segment tree?

vae371 · 2017-10-31 08:43:37

ld_xixi 发表于 2017-10-31 08:25
interval排个序，然后跟二分跟start比？

恩，但这个还不是最优解

ld_xixi · 2017-10-31 09:02:52

vae371 发表于 2017-10-31 08:43
恩，但这个还不是最优解

求指教，怎么招也得排一把序吧