FB 电面

gl891011 发表于 2015-8-20 04:54
楼主是new grad吗？

是的            

区间覆盖问题, 应该是线段树吧

暴力解法是不是找出所有起点中的最小值 minstart，找出所有终点的最大值 minend，然后for every integer in the range of [a,b] 看看落在几个区间，用maxcount记录？
这个时间复杂度应该是o(n^2)吧，还有没有更好的方法了呀

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

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

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

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

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

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

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

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

hbsophia 发表于 2015-9-11 13:24
好方法，只是要是有一个区间，比如［3，100000］这种，岂不是要把中间的每一个integer 都放hashmap, 岂不 ...

就是空间换时间嘛，要是遍历，也得从3遍历到100000的每个数，看在各个区间的个数对吧

这个题，把所有线段的起始点和终点排序，然后遍历，设置一个counter，遇到起始点就加1，遇到终点就减1，找counter的最大值就可以了。注意排序的时候，如果一个起始点和一个终点的值相同，起始点放前面。

哈哈哈大雄 发表于 2015-9-20 01:37
这个题，把所有线段的起始点和终点排序，然后遍历，设置一个counter，遇到起始点就加1，遇到终点就减1，找c ...

仍然是n^2