h*****g 发帖数: 312 | 1 A period of time where users login and logout, given a sets of login and
logout time pairs, write a function that can show the number of users online
at any given time.
http://www.glassdoor.com/Interview/A-period-of-time-where-users
我感觉直接scan 就行啊 从头到尾 看在哪个区间里, O(n)?
glassdoor 上给的answer 怎么那么复杂呢? 又sort, 又用什么tree的? | w****x 发帖数: 2483 | 2 就是排序所有时间端点, 然后那个时间点上begin points - end points就是当前在线
人数 | L***Q 发帖数: 508 | 3 我估计这题的意思是给定一个login/logout 时间的set,每次给你一个time,你的
function返回那个time在线人数。
那么每次function都去scan一遍效率就挺低了。应该是有个预处理,然后给一个time,
能很快返回在线人数,不需要去scan原来的set。
我瞎猜的哈
online
【在 h*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : A period of time where users login and logout, given a sets of login and : logout time pairs, write a function that can show the number of users online : at any given time. : http://www.glassdoor.com/Interview/A-period-of-time-where-users : 我感觉直接scan 就行啊 从头到尾 看在哪个区间里, O(n)? : glassdoor 上给的answer 怎么那么复杂呢? 又sort, 又用什么tree的?
| w****x 发帖数: 2483 | 4
预处理因该就是, 还是先按时间端点排序, 遍历一遍时间小段, 记录时间小段的在线人
数, 就是根据开始点-结束点算, 对于给定时间点做binary search定位到时间小段并返
回在线人数
【在 L***Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我估计这题的意思是给定一个login/logout 时间的set,每次给你一个time,你的 : function返回那个time在线人数。 : 那么每次function都去scan一遍效率就挺低了。应该是有个预处理,然后给一个time, : 能很快返回在线人数,不需要去scan原来的set。 : 我瞎猜的哈 : : online
| h*****g 发帖数: 312 | 5 en it is reasonable
【在 L***Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我估计这题的意思是给定一个login/logout 时间的set,每次给你一个time,你的 : function返回那个time在线人数。 : 那么每次function都去scan一遍效率就挺低了。应该是有个预处理,然后给一个time, : 能很快返回在线人数,不需要去scan原来的set。 : 我瞎猜的哈 : : online
| p*****2 发帖数: 21240 | 6 a period of time是多大,given time的单位是什么。 | p*****2 发帖数: 21240 | 7
能详细再谈一下吗。这题我想研究一下。你是按start排序吗?
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 预处理因该就是, 还是先按时间端点排序, 遍历一遍时间小段, 记录时间小段的在线人 : 数, 就是根据开始点-结束点算, 对于给定时间点做binary search定位到时间小段并返 : 回在线人数
| w****x 发帖数: 2483 | 8
1. 任何一个时间段(login time & logout time)都是由两个端点(login logout)组成,
首先不分端点是login还是logout对所有端点排序. 然后遍历整个数轴, 对每个端点和
端点之间的小段, 记录其在线人数(当前的login端点数 - 当前logout端点数), 这步是
算预处理, O(n)
2. 因为用户login, logout都是按时间顺序的, 所以可以很轻松的动态维护这个数轴.
3. 当需要查询一个时间点用户数的时候, 用binary search找出这个时间点坐落于哪个
时间小段, 这个时间小段对应的在线用户数就是答案(logn)
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 能详细再谈一下吗。这题我想研究一下。你是按start排序吗?
| p*****2 发帖数: 21240 | 9
成,
第一步最复杂,比如{1,3}, {5,7}
你首先得把1,3,5,7放到一个数组里排序吧?
然后你找小段
{1,3} 你要遍历一边所有的{login, logout} 找总数吗?
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 1. 任何一个时间段(login time & logout time)都是由两个端点(login logout)组成, : 首先不分端点是login还是logout对所有端点排序. 然后遍历整个数轴, 对每个端点和 : 端点之间的小段, 记录其在线人数(当前的login端点数 - 当前logout端点数), 这步是 : 算预处理, O(n) : 2. 因为用户login, logout都是按时间顺序的, 所以可以很轻松的动态维护这个数轴. : 3. 当需要查询一个时间点用户数的时候, 用binary search找出这个时间点坐落于哪个 : 时间小段, 这个时间小段对应的在线用户数就是答案(logn)
| w****x 发帖数: 2483 | 10
举个例子{1, 5} {2, 6} {3, 4}
==> 1(in), 2(in), 3(in), 4(out), 5(out), 6(out)
==>维护一个计数, 遇到login的+1, logout的-1
==>遍历时间点的所有小段:
<1,2> --> 1 <2,3> -->1+1 = 2 <3, 4> --> 2+1 = 3
<4, 5> --> 3 - 1 = 2 <5, 6> --> 2 - 1 = 1 <6, +无穷> --> 1 - 1 = 0
==>给各时间比如4.3, 做binary search 找到对应的小段 --> <4, 5> -->在线人数是
2
"你要遍历一边所有的{login, logout} 找总数吗" -->当然不用, 如果有cover住{1, 3}的
会有一个login point在1前面或{1,3}中间,in which case {1,3}就不算一个小段了
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 成, : 第一步最复杂,比如{1,3}, {5,7} : 你首先得把1,3,5,7放到一个数组里排序吧? : 然后你找小段 : {1,3} 你要遍历一边所有的{login, logout} 找总数吗?
| | | s******t 发帖数: 169 | 11 离散化+线段树可以做,或者离散化+树状数组,对于每个pair,直接插入,时间为log(
n),总共为nlog(n)。然后查询的时候,每次查询log(n)
wwwyhx说的本质上就是离散化吧,如果我没理解错的话。本质上相当于把一个相当大的
区间离散成较小的区间,比如说有一个对是(1,100000)另一个是(2,300000),真用一个
300000的数组去存就不太划算了,其实把几个点排下序然后离散化,4个点就可以 | w****x 发帖数: 2483 | 12
log(
不用真的拿300000的来做啊, 这么做的话float就没法整了, 就用结构体就可以了, 比如
struct TIME_POINT
{
bool bLogin;
float fTimePoint;
};
如果拿300000来做, 直接都不用binary search了
【在 s******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 离散化+线段树可以做,或者离散化+树状数组,对于每个pair,直接插入,时间为log( : n),总共为nlog(n)。然后查询的时候,每次查询log(n) : wwwyhx说的本质上就是离散化吧,如果我没理解错的话。本质上相当于把一个相当大的 : 区间离散成较小的区间,比如说有一个对是(1,100000)另一个是(2,300000),真用一个 : 300000的数组去存就不太划算了,其实把几个点排下序然后离散化,4个点就可以
| z*y 发帖数: 1311 | 13
online
每个user是一个区间,query是一个点
用interval tree
【在 h*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : A period of time where users login and logout, given a sets of login and : logout time pairs, write a function that can show the number of users online : at any given time. : http://www.glassdoor.com/Interview/A-period-of-time-where-users : 我感觉直接scan 就行啊 从头到尾 看在哪个区间里, O(n)? : glassdoor 上给的answer 怎么那么复杂呢? 又sort, 又用什么tree的?
| p*****2 发帖数: 21240 | 14
3}的
不错的idea。赞一个。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : log( : 不用真的拿300000的来做啊, 这么做的话float就没法整了, 就用结构体就可以了, 比如 : struct TIME_POINT : { : bool bLogin; : float fTimePoint; : }; : 如果拿300000来做, 直接都不用binary search了
| p*****2 发帖数: 21240 | 15
3}的
要不要搞一个可以动态添加{login,longout}的算法呢?
感觉应用上应该是动态添加的吧?
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : log( : 不用真的拿300000的来做啊, 这么做的话float就没法整了, 就用结构体就可以了, 比如 : struct TIME_POINT : { : bool bLogin; : float fTimePoint; : }; : 如果拿300000来做, 直接都不用binary search了
| w****x 发帖数: 2483 | 16
所有的user的login logout时间都是自然按顺序的, 因该没啥问题.维护一个integer代
表当前用户数, login一个产生一个时间小段, 就是integer++, logout 一个又产生一
个时间小段, integer--
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 3}的 : 要不要搞一个可以动态添加{login,longout}的算法呢? : 感觉应用上应该是动态添加的吧?
| p*****2 发帖数: 21240 | 17
login, logout产生是以logout为主的。所以login可能是很早以前。这样就需要更新以
前有overlap的小段。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 所有的user的login logout时间都是自然按顺序的, 因该没啥问题.维护一个integer代 : 表当前用户数, login一个产生一个时间小段, 就是integer++, logout 一个又产生一 : 个时间小段, integer--
| w****x 发帖数: 2483 | 18
不需要, 以前的小段代表在那个时间段有多少人在线, 过了那个时间段不管是什么情况
, 历史数据都不会改变. 比如我<9, 10> ==> 100, 代表9点到10点100人恒定在线, 那
之后不管登陆登出9点到10点这个历史在线人数永远不会改变
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : login, logout产生是以logout为主的。所以login可能是很早以前。这样就需要更新以 : 前有overlap的小段。
| h*****g 发帖数: 312 | 19 niu
3}的
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 不需要, 以前的小段代表在那个时间段有多少人在线, 过了那个时间段不管是什么情况 : , 历史数据都不会改变. 比如我<9, 10> ==> 100, 代表9点到10点100人恒定在线, 那 : 之后不管登陆登出9点到10点这个历史在线人数永远不会改变
| p*****2 发帖数: 21240 | 20
我想到的是logout以后在把数据加入进来。不过确实即使没有logout,login也应该算
进去。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 不需要, 以前的小段代表在那个时间段有多少人在线, 过了那个时间段不管是什么情况 : , 历史数据都不会改变. 比如我<9, 10> ==> 100, 代表9点到10点100人恒定在线, 那 : 之后不管登陆登出9点到10点这个历史在线人数永远不会改变
| c****p 发帖数: 6474 | 21 把所有事件在时间轴上排序。
如果数据源是log的话直接按顺序插入就好了。
时间轴上的事件点保留两个信息就可以了:<时间,当前在线人数>
对于相连的、发生在T_i和T_i+1的两个事件,时间段[T_i, T_i+1)的在线人数就等于T_
i事件的当前在线人数。
应该不用考虑记录的增删问题,要加也是在数轴的后端加,不会影响已排序部分。【
在 huameng (huameng) 的大作中提到: 】
online | C***U 发帖数: 2406 | 22 这个题目和interval相交个数那个差不多
可以转换成数括号
A period of time where users login and logout, given a sets of login and
logout time pai........
★ Sent from iPhone App: iReader Mitbbs 7.52 - iPad Lite
【在 h*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : A period of time where users login and logout, given a sets of login and : logout time pairs, write a function that can show the number of users online : at any given time. : http://www.glassdoor.com/Interview/A-period-of-time-where-users : 我感觉直接scan 就行啊 从头到尾 看在哪个区间里, O(n)? : glassdoor 上给的answer 怎么那么复杂呢? 又sort, 又用什么tree的?
|
|