问个Facebook 电面题# JobHunting - 待字闺中
w*x
1 楼
giving lots of intervals [ai, bi], find a point intersect with the most
number of intervals
要nlogn的解法哦, 要写程序的, segment tree就算了
number of intervals
要nlogn的解法哦, 要写程序的, segment tree就算了
w*x
2 楼
不是我面的, glassdoor上的
P*U
3 楼
排序+扫描线？
w*x
4 楼
具体点了大哥
【在 P*******U 的大作中提到】
: 排序+扫描线？
w*x
5 楼
我觉得先按所有的end point排序, 比如 (1.1, 3.2) (2.2, 2.4) (0.3, 2.3)
==> 0.3, 1.1, 2.2, 2.3, 2.4, 3.2
这样相邻两端形成的线段就是最小的segment, 对每个atomic segment求中点.
比如0.3 - 1.1的取0.7, 然后判断0.7落在几个segment.
不过这样好像只能用线段树???
==> 0.3, 1.1, 2.2, 2.3, 2.4, 3.2
这样相邻两端形成的线段就是最小的segment, 对每个atomic segment求中点.
比如0.3 - 1.1的取0.7, 然后判断0.7落在几个segment.
不过这样好像只能用线段树???
g*e
6 楼
假设总体interval的范围是[A,B]
1.所有interval按照ai排序 (nlogn)
2.count the number of intervals that intersect (A+B)/2 O(n)
3.recursively do 1 & 2 for F(A,(A+B)/2), F((A+B)/2, B), update the maximun
intersect count
4.base case是一个区间里没有完整的一个interval
跟merge sort差不多思路
time complexity
f(n)=2*f(n/2)+O(n)
根据master theorem 总体时间nlogn
故总体时间还是nlogn
1.所有interval按照ai排序 (nlogn)
2.count the number of intervals that intersect (A+B)/2 O(n)
3.recursively do 1 & 2 for F(A,(A+B)/2), F((A+B)/2, B), update the maximun
intersect count
4.base case是一个区间里没有完整的一个interval
跟merge sort差不多思路
time complexity
f(n)=2*f(n/2)+O(n)
根据master theorem 总体时间nlogn
故总体时间还是nlogn
u*r
7 楼
把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
就在k与k+1之间.
后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
就在k与k+1之间.
s*n
8 楼
第3步看不懂
【在 g*********e 的大作中提到】
: 假设总体interval的范围是[A,B]
: 1.所有interval按照ai排序 (nlogn)
: 2.count the number of intervals that intersect (A+B)/2 O(n)
: 3.recursively do 1 & 2 for F(A,(A+B)/2), F((A+B)/2, B), update the maximun
: intersect count
: 4.base case是一个区间里没有完整的一个interval
: 跟merge sort差不多思路
: time complexity
: f(n)=2*f(n/2)+O(n)
: 根据master theorem 总体时间nlogn
【在 g*********e 的大作中提到】
: 假设总体interval的范围是[A,B]
: 1.所有interval按照ai排序 (nlogn)
: 2.count the number of intervals that intersect (A+B)/2 O(n)
: 3.recursively do 1 & 2 for F(A,(A+B)/2), F((A+B)/2, B), update the maximun
: intersect count
: 4.base case是一个区间里没有完整的一个interval
: 跟merge sort差不多思路
: time complexity
: f(n)=2*f(n/2)+O(n)
: 根据master theorem 总体时间nlogn
R*9
9 楼
8cuo
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
s*n
10 楼
恩，这是标准答案，以前看过都忘了。。。
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
g*e
11 楼
F(A,B)用来计算包含在[A,B]里的最大overlap数
不过我楼下方法更好
【在 s******n 的大作中提到】
: 第3步看不懂
c*g
12 楼
没看明白什么意思，什么叫 find a point?
难道这样的点不是有无限个么？ 就算确定坐标是整数，也应该有好多个吧？
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
难道这样的点不是有无限个么？ 就算确定坐标是整数，也应该有好多个吧？
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
c*g
13 楼
精确到多少位？
如果不说精确到小数多少位，应该是无限个吧？
【在 w****x 的大作中提到】
: 我觉得先按所有的end point排序, 比如 (1.1, 3.2) (2.2, 2.4) (0.3, 2.3)
: ==> 0.3, 1.1, 2.2, 2.3, 2.4, 3.2
: 这样相邻两端形成的线段就是最小的segment, 对每个atomic segment求中点.
: 比如0.3 - 1.1的取0.7, 然后判断0.7落在几个segment.
: 不过这样好像只能用线段树???
如果不说精确到小数多少位，应该是无限个吧？
【在 w****x 的大作中提到】
: 我觉得先按所有的end point排序, 比如 (1.1, 3.2) (2.2, 2.4) (0.3, 2.3)
: ==> 0.3, 1.1, 2.2, 2.3, 2.4, 3.2
: 这样相邻两端形成的线段就是最小的segment, 对每个atomic segment求中点.
: 比如0.3 - 1.1的取0.7, 然后判断0.7落在几个segment.
: 不过这样好像只能用线段树???
c*g
14 楼
能解释一下么？
什么叫“从头扫描到尾”
什么叫"碰到a"?
每次只能碰到一个点，然后再去判断是a还是b，并且判断是哪个index,这个过程需要时
间吧？
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
什么叫“从头扫描到尾”
什么叫"碰到a"?
每次只能碰到一个点，然后再去判断是a还是b，并且判断是哪个index,这个过程需要时
间吧？
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
u*r
15 楼
扫描由ai,bi构成的长度为2n的序列.
假设包含ai,bi所有点的长度为2n的序列叫D,需要同时保存另一个长度为2n的雪列L,如
果D[i]是区间起点(ai),L[i]=1,否则L[i]=0.对D排序的时候同时调整L,这样判断是a还
是b的时间复杂度是O(1).
【在 c***g 的大作中提到】
: 能解释一下么？
: 什么叫“从头扫描到尾”
: 什么叫"碰到a"?
: 每次只能碰到一个点，然后再去判断是a还是b，并且判断是哪个index,这个过程需要时
: 间吧？
S*0
16 楼
哎呀!!!!!!!!!!!! 对啊
以前做过这题, 是这么做的, 这题丢电面是不是太扯了
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
C*U
17 楼
这个相当于是嵌套最多的括号
nlogn可以做到的
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
nlogn可以做到的
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
c*n
18 楼
Sort all N intervals by begin and end time respectively, saying B[] and E[]
, for each Interval I(begin, end), find number of intervals with begin time
later than I.end, A, and number of intervals with end time early than I.
begin, B. Then the the number of intervals intersecting with I is N - A - B
- 1. As B[] and E[] are sorted array, A and B can be calculated in lgN, so
total time is nlogn.
, for each Interval I(begin, end), find number of intervals with begin time
later than I.end, A, and number of intervals with end time early than I.
begin, B. Then the the number of intervals intersecting with I is N - A - B
- 1. As B[] and E[] are sorted array, A and B can be calculated in lgN, so
total time is nlogn.
A*u
19 楼
聪明
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
d*0
20 楼
漂亮
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
w*x
21 楼
giving lots of intervals [ai, bi], find a point intersect with the most
number of intervals
要nlogn的解法哦, 要写程序的, segment tree就算了
number of intervals
要nlogn的解法哦, 要写程序的, segment tree就算了
w*x
22 楼
不是我面的, glassdoor上的
P*U
23 楼
排序+扫描线？
w*x
24 楼
具体点了大哥
【在 P*******U 的大作中提到】
: 排序+扫描线？
w*x
25 楼
我觉得先按所有的end point排序, 比如 (1.1, 3.2) (2.2, 2.4) (0.3, 2.3)
==> 0.3, 1.1, 2.2, 2.3, 2.4, 3.2
这样相邻两端形成的线段就是最小的segment, 对每个atomic segment求中点.
比如0.3 - 1.1的取0.7, 然后判断0.7落在几个segment.
不过这样好像只能用线段树???
==> 0.3, 1.1, 2.2, 2.3, 2.4, 3.2
这样相邻两端形成的线段就是最小的segment, 对每个atomic segment求中点.
比如0.3 - 1.1的取0.7, 然后判断0.7落在几个segment.
不过这样好像只能用线段树???
g*e
26 楼
假设总体interval的范围是[A,B]
1.所有interval按照ai排序 (nlogn)
2.count the number of intervals that intersect (A+B)/2 O(n)
3.recursively do 1 & 2 for F(A,(A+B)/2), F((A+B)/2, B), update the maximun
intersect count
4.base case是一个区间里没有完整的一个interval
跟merge sort差不多思路
time complexity
f(n)=2*f(n/2)+O(n)
根据master theorem 总体时间nlogn
故总体时间还是nlogn
1.所有interval按照ai排序 (nlogn)
2.count the number of intervals that intersect (A+B)/2 O(n)
3.recursively do 1 & 2 for F(A,(A+B)/2), F((A+B)/2, B), update the maximun
intersect count
4.base case是一个区间里没有完整的一个interval
跟merge sort差不多思路
time complexity
f(n)=2*f(n/2)+O(n)
根据master theorem 总体时间nlogn
故总体时间还是nlogn
u*r
27 楼
把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
就在k与k+1之间.
后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
就在k与k+1之间.
s*n
28 楼
第3步看不懂
【在 g*********e 的大作中提到】
: 假设总体interval的范围是[A,B]
: 1.所有interval按照ai排序 (nlogn)
: 2.count the number of intervals that intersect (A+B)/2 O(n)
: 3.recursively do 1 & 2 for F(A,(A+B)/2), F((A+B)/2, B), update the maximun
: intersect count
: 4.base case是一个区间里没有完整的一个interval
: 跟merge sort差不多思路
: time complexity
: f(n)=2*f(n/2)+O(n)
: 根据master theorem 总体时间nlogn
【在 g*********e 的大作中提到】
: 假设总体interval的范围是[A,B]
: 1.所有interval按照ai排序 (nlogn)
: 2.count the number of intervals that intersect (A+B)/2 O(n)
: 3.recursively do 1 & 2 for F(A,(A+B)/2), F((A+B)/2, B), update the maximun
: intersect count
: 4.base case是一个区间里没有完整的一个interval
: 跟merge sort差不多思路
: time complexity
: f(n)=2*f(n/2)+O(n)
: 根据master theorem 总体时间nlogn
R*9
29 楼
8cuo
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
s*n
30 楼
恩，这是标准答案，以前看过都忘了。。。
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
g*e
31 楼
F(A,B)用来计算包含在[A,B]里的最大overlap数
不过我楼下方法更好
【在 s******n 的大作中提到】
: 第3步看不懂
c*g
32 楼
没看明白什么意思，什么叫 find a point?
难道这样的点不是有无限个么？ 就算确定坐标是整数，也应该有好多个吧？
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
难道这样的点不是有无限个么？ 就算确定坐标是整数，也应该有好多个吧？
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
c*g
33 楼
精确到多少位？
如果不说精确到小数多少位，应该是无限个吧？
【在 w****x 的大作中提到】
: 我觉得先按所有的end point排序, 比如 (1.1, 3.2) (2.2, 2.4) (0.3, 2.3)
: ==> 0.3, 1.1, 2.2, 2.3, 2.4, 3.2
: 这样相邻两端形成的线段就是最小的segment, 对每个atomic segment求中点.
: 比如0.3 - 1.1的取0.7, 然后判断0.7落在几个segment.
: 不过这样好像只能用线段树???
如果不说精确到小数多少位，应该是无限个吧？
【在 w****x 的大作中提到】
: 我觉得先按所有的end point排序, 比如 (1.1, 3.2) (2.2, 2.4) (0.3, 2.3)
: ==> 0.3, 1.1, 2.2, 2.3, 2.4, 3.2
: 这样相邻两端形成的线段就是最小的segment, 对每个atomic segment求中点.
: 比如0.3 - 1.1的取0.7, 然后判断0.7落在几个segment.
: 不过这样好像只能用线段树???
c*g
34 楼
能解释一下么？
什么叫“从头扫描到尾”
什么叫"碰到a"?
每次只能碰到一个点，然后再去判断是a还是b，并且判断是哪个index,这个过程需要时
间吧？
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
什么叫“从头扫描到尾”
什么叫"碰到a"?
每次只能碰到一个点，然后再去判断是a还是b，并且判断是哪个index,这个过程需要时
间吧？
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
u*r
35 楼
扫描由ai,bi构成的长度为2n的序列.
假设包含ai,bi所有点的长度为2n的序列叫D,需要同时保存另一个长度为2n的雪列L,如
果D[i]是区间起点(ai),L[i]=1,否则L[i]=0.对D排序的时候同时调整L,这样判断是a还
是b的时间复杂度是O(1).
【在 c***g 的大作中提到】
: 能解释一下么？
: 什么叫“从头扫描到尾”
: 什么叫"碰到a"?
: 每次只能碰到一个点，然后再去判断是a还是b，并且判断是哪个index,这个过程需要时
: 间吧？
S*0
36 楼
哎呀!!!!!!!!!!!! 对啊
以前做过这题, 是这么做的, 这题丢电面是不是太扯了
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
C*U
37 楼
这个相当于是嵌套最多的括号
nlogn可以做到的
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
nlogn可以做到的
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
c*n
38 楼
Sort all N intervals by begin and end time respectively, saying B[] and E[]
, for each Interval I(begin, end), find number of intervals with begin time
later than I.end, A, and number of intervals with end time early than I.
begin, B. Then the the number of intervals intersecting with I is N - A - B
- 1. As B[] and E[] are sorted array, A and B can be calculated in lgN, so
total time is nlogn.
, for each Interval I(begin, end), find number of intervals with begin time
later than I.end, A, and number of intervals with end time early than I.
begin, B. Then the the number of intervals intersecting with I is N - A - B
- 1. As B[] and E[] are sorted array, A and B can be calculated in lgN, so
total time is nlogn.
A*u
39 楼
聪明
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
d*0
40 楼
漂亮
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
h*g
41 楼
还是没懂，谁能给详细解释下？
最好给个例子
【在 u**r 的大作中提到】
:
: 扫描由ai,bi构成的长度为2n的序列.
: 假设包含ai,bi所有点的长度为2n的序列叫D,需要同时保存另一个长度为2n的雪列L,如
: 果D[i]是区间起点(ai),L[i]=1,否则L[i]=0.对D排序的时候同时调整L,这样判断是a还
: 是b的时间复杂度是O(1).
最好给个例子
【在 u**r 的大作中提到】
:
: 扫描由ai,bi构成的长度为2n的序列.
: 假设包含ai,bi所有点的长度为2n的序列叫D,需要同时保存另一个长度为2n的雪列L,如
: 果D[i]是区间起点(ai),L[i]=1,否则L[i]=0.对D排序的时候同时调整L,这样判断是a还
: 是b的时间复杂度是O(1).
d*y
42 楼
这是Introduction to Algorithms书上的课后题。
是Point of Most intersection( POM)问题。
用sweep line algorithm，要点是将每个区间的左右端点分开并排序，
得到2n个end point数组，简单的做法可以将2N个端点augment +1 和-1计数，
也可以在扫描过程中维持一个当前仍然被交叉的区间的集合（用二叉树），插入和删除
都是log n
这样的算法不仅可以计数还可以输出哪些区间有交叉。
另外还可以变形为求和其他区间交叉最多的segment，
这时需要再保持额外的数据结构，比如当前端点处已经扫描过的左端点数量。
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
是Point of Most intersection( POM)问题。
用sweep line algorithm，要点是将每个区间的左右端点分开并排序，
得到2n个end point数组，简单的做法可以将2N个端点augment +1 和-1计数，
也可以在扫描过程中维持一个当前仍然被交叉的区间的集合（用二叉树），插入和删除
都是log n
这样的算法不仅可以计数还可以输出哪些区间有交叉。
另外还可以变形为求和其他区间交叉最多的segment，
这时需要再保持额外的数据结构，比如当前端点处已经扫描过的左端点数量。
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
C*U
43 楼
这题问了好多次了
可以把他们转化成()的算法
a_i=(, b_i=)
然后把它们根据大小排成一列。 这里用nlogn的时间。
然后你从第一位开始走，
遇到(就+1 遇到)就-1
把所有的数 记录下来 最大的数就是你要的答案了。
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
可以把他们转化成()的算法
a_i=(, b_i=)
然后把它们根据大小排成一列。 这里用nlogn的时间。
然后你从第一位开始走，
遇到(就+1 遇到)就-1
把所有的数 记录下来 最大的数就是你要的答案了。
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
l*8
44 楼
Input intevals: [10 25] [20 45] [30 48] [40 44] [50 55]
Step 1:
sort all the numbers and mark '+1' if the number is the start of an interval
, mark '-1' if the number is the end of an interval.
10 20 25 30 40 44 45 48 50 55
+1 +1 -1 +1 +1 -1 -1 -1 +1 -1
Step 2:
accumulate the markers:
1 2 1 2 3 2 1 0 1 0
The largest one during the accumulation is 3, which corresponds to [40 44].
So every point inside [40 44] intersect with 3 intervals.
【在 h*****g 的大作中提到】
: 还是没懂，谁能给详细解释下？
: 最好给个例子
Step 1:
sort all the numbers and mark '+1' if the number is the start of an interval
, mark '-1' if the number is the end of an interval.
10 20 25 30 40 44 45 48 50 55
+1 +1 -1 +1 +1 -1 -1 -1 +1 -1
Step 2:
accumulate the markers:
1 2 1 2 3 2 1 0 1 0
The largest one during the accumulation is 3, which corresponds to [40 44].
So every point inside [40 44] intersect with 3 intervals.
【在 h*****g 的大作中提到】
: 还是没懂，谁能给详细解释下？
: 最好给个例子
h*g
45 楼
十分感谢！
interval
.
【在 l*********8 的大作中提到】
: Input intevals: [10 25] [20 45] [30 48] [40 44] [50 55]
: Step 1:
: sort all the numbers and mark '+1' if the number is the start of an interval
: , mark '-1' if the number is the end of an interval.
: 10 20 25 30 40 44 45 48 50 55
: +1 +1 -1 +1 +1 -1 -1 -1 +1 -1
: Step 2:
: accumulate the markers:
: 1 2 1 2 3 2 1 0 1 0
: The largest one during the accumulation is 3, which corresponds to [40 44].
interval
.
【在 l*********8 的大作中提到】
: Input intevals: [10 25] [20 45] [30 48] [40 44] [50 55]
: Step 1:
: sort all the numbers and mark '+1' if the number is the start of an interval
: , mark '-1' if the number is the end of an interval.
: 10 20 25 30 40 44 45 48 50 55
: +1 +1 -1 +1 +1 -1 -1 -1 +1 -1
: Step 2:
: accumulate the markers:
: 1 2 1 2 3 2 1 0 1 0
: The largest one during the accumulation is 3, which corresponds to [40 44].
h*a
46 楼
What if the endpoint of one interval is also the starting point of another
interval, how do we put the marks?
Thanks.
interval
.
【在 l*********8 的大作中提到】
: Input intevals: [10 25] [20 45] [30 48] [40 44] [50 55]
: Step 1:
: sort all the numbers and mark '+1' if the number is the start of an interval
: , mark '-1' if the number is the end of an interval.
: 10 20 25 30 40 44 45 48 50 55
: +1 +1 -1 +1 +1 -1 -1 -1 +1 -1
: Step 2:
: accumulate the markers:
: 1 2 1 2 3 2 1 0 1 0
: The largest one during the accumulation is 3, which corresponds to [40 44].
interval, how do we put the marks?
Thanks.
interval
.
【在 l*********8 的大作中提到】
: Input intevals: [10 25] [20 45] [30 48] [40 44] [50 55]
: Step 1:
: sort all the numbers and mark '+1' if the number is the start of an interval
: , mark '-1' if the number is the end of an interval.
: 10 20 25 30 40 44 45 48 50 55
: +1 +1 -1 +1 +1 -1 -1 -1 +1 -1
: Step 2:
: accumulate the markers:
: 1 2 1 2 3 2 1 0 1 0
: The largest one during the accumulation is 3, which corresponds to [40 44].
l*8
47 楼
如果每个interval包括起始点，不包括结束点
[10 20) [20 40)
10 20 20 40
+1 -1 +1 -1
如果每个interval包括起始点和结束点
[10 20] [20 40]
10 20 20 40
+1 +1 -1 -1
或者先把这样的interval合并
【在 h****a 的大作中提到】
: What if the endpoint of one interval is also the starting point of another
: interval, how do we put the marks?
: Thanks.
:
: interval
: .
[10 20) [20 40)
10 20 20 40
+1 -1 +1 -1
如果每个interval包括起始点和结束点
[10 20] [20 40]
10 20 20 40
+1 +1 -1 -1
或者先把这样的interval合并
【在 h****a 的大作中提到】
: What if the endpoint of one interval is also the starting point of another
: interval, how do we put the marks?
: Thanks.
:
: interval
: .
h*g
48 楼
还是没懂，谁能给详细解释下？
最好给个例子
【在 u**r 的大作中提到】
:
: 扫描由ai,bi构成的长度为2n的序列.
: 假设包含ai,bi所有点的长度为2n的序列叫D,需要同时保存另一个长度为2n的雪列L,如
: 果D[i]是区间起点(ai),L[i]=1,否则L[i]=0.对D排序的时候同时调整L,这样判断是a还
: 是b的时间复杂度是O(1).
最好给个例子
【在 u**r 的大作中提到】
:
: 扫描由ai,bi构成的长度为2n的序列.
: 假设包含ai,bi所有点的长度为2n的序列叫D,需要同时保存另一个长度为2n的雪列L,如
: 果D[i]是区间起点(ai),L[i]=1,否则L[i]=0.对D排序的时候同时调整L,这样判断是a还
: 是b的时间复杂度是O(1).
d*y
49 楼
这是Introduction to Algorithms书上的课后题。
是Point of Most intersection( POM)问题。
用sweep line algorithm，要点是将每个区间的左右端点分开并排序，
得到2n个end point数组，简单的做法可以将2N个端点augment +1 和-1计数，
也可以在扫描过程中维持一个当前仍然被交叉的区间的集合（用二叉树），插入和删除
都是log n
这样的算法不仅可以计数还可以输出哪些区间有交叉。
另外还可以变形为求和其他区间交叉最多的segment，
这时需要再保持额外的数据结构，比如当前端点处已经扫描过的左端点数量。
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
是Point of Most intersection( POM)问题。
用sweep line algorithm，要点是将每个区间的左右端点分开并排序，
得到2n个end point数组，简单的做法可以将2N个端点augment +1 和-1计数，
也可以在扫描过程中维持一个当前仍然被交叉的区间的集合（用二叉树），插入和删除
都是log n
这样的算法不仅可以计数还可以输出哪些区间有交叉。
另外还可以变形为求和其他区间交叉最多的segment，
这时需要再保持额外的数据结构，比如当前端点处已经扫描过的左端点数量。
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
C*U
50 楼
这题问了好多次了
可以把他们转化成()的算法
a_i=(, b_i=)
然后把它们根据大小排成一列。 这里用nlogn的时间。
然后你从第一位开始走，
遇到(就+1 遇到)就-1
把所有的数 记录下来 最大的数就是你要的答案了。
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
可以把他们转化成()的算法
a_i=(, b_i=)
然后把它们根据大小排成一列。 这里用nlogn的时间。
然后你从第一位开始走，
遇到(就+1 遇到)就-1
把所有的数 记录下来 最大的数就是你要的答案了。
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
l*8
51 楼
Input intevals: [10 25] [20 45] [30 48] [40 44] [50 55]
Step 1:
sort all the numbers and mark '+1' if the number is the start of an interval
, mark '-1' if the number is the end of an interval.
10 20 25 30 40 44 45 48 50 55
+1 +1 -1 +1 +1 -1 -1 -1 +1 -1
Step 2:
accumulate the markers:
1 2 1 2 3 2 1 0 1 0
The largest one during the accumulation is 3, which corresponds to [40 44].
So every point inside [40 44] intersect with 3 intervals.
【在 h*****g 的大作中提到】
: 还是没懂，谁能给详细解释下？
: 最好给个例子
Step 1:
sort all the numbers and mark '+1' if the number is the start of an interval
, mark '-1' if the number is the end of an interval.
10 20 25 30 40 44 45 48 50 55
+1 +1 -1 +1 +1 -1 -1 -1 +1 -1
Step 2:
accumulate the markers:
1 2 1 2 3 2 1 0 1 0
The largest one during the accumulation is 3, which corresponds to [40 44].
So every point inside [40 44] intersect with 3 intervals.
【在 h*****g 的大作中提到】
: 还是没懂，谁能给详细解释下？
: 最好给个例子
h*g
52 楼
十分感谢！
interval
.
【在 l*********8 的大作中提到】
: Input intevals: [10 25] [20 45] [30 48] [40 44] [50 55]
: Step 1:
: sort all the numbers and mark '+1' if the number is the start of an interval
: , mark '-1' if the number is the end of an interval.
: 10 20 25 30 40 44 45 48 50 55
: +1 +1 -1 +1 +1 -1 -1 -1 +1 -1
: Step 2:
: accumulate the markers:
: 1 2 1 2 3 2 1 0 1 0
: The largest one during the accumulation is 3, which corresponds to [40 44].
interval
.
【在 l*********8 的大作中提到】
: Input intevals: [10 25] [20 45] [30 48] [40 44] [50 55]
: Step 1:
: sort all the numbers and mark '+1' if the number is the start of an interval
: , mark '-1' if the number is the end of an interval.
: 10 20 25 30 40 44 45 48 50 55
: +1 +1 -1 +1 +1 -1 -1 -1 +1 -1
: Step 2:
: accumulate the markers:
: 1 2 1 2 3 2 1 0 1 0
: The largest one during the accumulation is 3, which corresponds to [40 44].
h*a
53 楼
What if the endpoint of one interval is also the starting point of another
interval, how do we put the marks?
Thanks.
interval
.
【在 l*********8 的大作中提到】
: Input intevals: [10 25] [20 45] [30 48] [40 44] [50 55]
: Step 1:
: sort all the numbers and mark '+1' if the number is the start of an interval
: , mark '-1' if the number is the end of an interval.
: 10 20 25 30 40 44 45 48 50 55
: +1 +1 -1 +1 +1 -1 -1 -1 +1 -1
: Step 2:
: accumulate the markers:
: 1 2 1 2 3 2 1 0 1 0
: The largest one during the accumulation is 3, which corresponds to [40 44].
interval, how do we put the marks?
Thanks.
interval
.
【在 l*********8 的大作中提到】
: Input intevals: [10 25] [20 45] [30 48] [40 44] [50 55]
: Step 1:
: sort all the numbers and mark '+1' if the number is the start of an interval
: , mark '-1' if the number is the end of an interval.
: 10 20 25 30 40 44 45 48 50 55
: +1 +1 -1 +1 +1 -1 -1 -1 +1 -1
: Step 2:
: accumulate the markers:
: 1 2 1 2 3 2 1 0 1 0
: The largest one during the accumulation is 3, which corresponds to [40 44].
l*8
54 楼
如果每个interval包括起始点，不包括结束点
[10 20) [20 40)
10 20 20 40
+1 -1 +1 -1
如果每个interval包括起始点和结束点
[10 20] [20 40]
10 20 20 40
+1 +1 -1 -1
或者先把这样的interval合并
【在 h****a 的大作中提到】
: What if the endpoint of one interval is also the starting point of another
: interval, how do we put the marks?
: Thanks.
:
: interval
: .
[10 20) [20 40)
10 20 20 40
+1 -1 +1 -1
如果每个interval包括起始点和结束点
[10 20] [20 40]
10 20 20 40
+1 +1 -1 -1
或者先把这样的interval合并
【在 h****a 的大作中提到】
: What if the endpoint of one interval is also the starting point of another
: interval, how do we put the marks?
: Thanks.
:
: interval
: .
P*r
55 楼
有个问题。是所有interval左右边界都是inclusive的吗？如果是的话，那是不是
target point就是边界中的一个呢。
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
target point就是边界中的一个呢。
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
相关阅读
拿到offer 去上班以前能申请h1b么？Amazon的Recruiter主动联系了我请问VSC的加急的fax number是多少?面试时不会的题目可以pass吗？纠结：怀孕了要不要告诉猎头和未来雇主？最早10月1号上班，现在找工作能行吗？面试要是碰到完全不熟的概念怎么办办11年的H1b应该怎么准备资料?能去别的学校的career fair吗Question about h1b thxGoogle onsite结果求祝福航空和石油的EE 哪个好？ 请问在哪里可以查 工资 ？ 谢谢今年似乎还没有报谷歌offer的大家愿意在Facebook和Twitter上面讨论找工作的事情吗？求推荐：面试用的黑皮portfolioAmazon offer + 面经 ... How to negotiate effectively?刚才去JOBMARKET版看到这个帖子，本想投简历，结果一看回复。瞎了Amazon is hiring senior UI/Front end Developers-Seattle/WAsysmind有人听说过么？说是咨询公司。有点ICC的感觉，这家是黑店么？还是正规的靠谱的？问一道今天在线测试的题目