w****x
发帖数: 2483 | 1 giving lots of intervals [ai, bi], find a point intersect with the most
number of intervals
要nlogn的解法哦, 要写程序的, segment tree就算了 | w****x
发帖数: 2483 | | P*******U
发帖数: 203 | | w****x
发帖数: 2483 | 4
具体点了大哥
【在 P*******U 的大作中提到】
: 排序+扫描线？
| w****x
发帖数: 2483 | 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.
不过这样好像只能用线段树??? | g*********e
发帖数: 14401 | 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 | u**r
发帖数: 663 | 7 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
就在k与k+1之间. | s******n
发帖数: 3946 | 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
| R******9
发帖数: 267 | 9 8cuo
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
| s******n
发帖数: 3946 | 10 恩，这是标准答案，以前看过都忘了。。。
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
| | | g*********e
发帖数: 14401 | 11
F(A,B)用来计算包含在[A,B]里的最大overlap数
不过我楼下方法更好
【在 s******n 的大作中提到】
: 第3步看不懂
| c***g
发帖数: 472 | 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就算了
| c***g
发帖数: 472 | 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.
: 不过这样好像只能用线段树???
| c***g
发帖数: 472 | 14 能解释一下么？
什么叫“从头扫描到尾”
什么叫"碰到a"?
每次只能碰到一个点，然后再去判断是a还是b，并且判断是哪个index,这个过程需要时
间吧？
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
| u**r
发帖数: 663 | 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
发帖数: 71 | 16
哎呀!!!!!!!!!!!! 对啊
以前做过这题, 是这么做的, 这题丢电面是不是太扯了
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
| C***U
发帖数: 2406 | 17 这个相当于是嵌套最多的括号
nlogn可以做到的
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
| c*****n
发帖数: 96 | 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. | A**u
发帖数: 2458 | 19 聪明
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
| d**0
发帖数: 124 | 20 漂亮
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
| | | w****x
发帖数: 2483 | 21 giving lots of intervals [ai, bi], find a point intersect with the most
number of intervals
要nlogn的解法哦, 要写程序的, segment tree就算了 | w****x
发帖数: 2483 | | P*******U
发帖数: 203 | | w****x
发帖数: 2483 | 24
具体点了大哥
【在 P*******U 的大作中提到】
: 排序+扫描线？
| w****x
发帖数: 2483 | 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.
不过这样好像只能用线段树??? | g*********e
发帖数: 14401 | 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 | u**r
发帖数: 663 | 27 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
就在k与k+1之间. | s******n
发帖数: 3946 | 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
| R******9
发帖数: 267 | 29 8cuo
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
| s******n
发帖数: 3946 | 30 恩，这是标准答案，以前看过都忘了。。。
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
| | | g*********e
发帖数: 14401 | 31
F(A,B)用来计算包含在[A,B]里的最大overlap数
不过我楼下方法更好
【在 s******n 的大作中提到】
: 第3步看不懂
| c***g
发帖数: 472 | 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就算了
| c***g
发帖数: 472 | 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.
: 不过这样好像只能用线段树???
| c***g
发帖数: 472 | 34 能解释一下么？
什么叫“从头扫描到尾”
什么叫"碰到a"?
每次只能碰到一个点，然后再去判断是a还是b，并且判断是哪个index,这个过程需要时
间吧？
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
| u**r
发帖数: 663 | 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
发帖数: 71 | 36
哎呀!!!!!!!!!!!! 对啊
以前做过这题, 是这么做的, 这题丢电面是不是太扯了
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
| C***U
发帖数: 2406 | 37 这个相当于是嵌套最多的括号
nlogn可以做到的
【在 w****x 的大作中提到】
: giving lots of intervals [ai, bi], find a point intersect with the most
: number of intervals
: 要nlogn的解法哦, 要写程序的, segment tree就算了
| c*****n
发帖数: 96 | 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. | A**u
发帖数: 2458 | 39 聪明
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
| d**0
发帖数: 124 | 40 漂亮
【在 u**r 的大作中提到】
: 把所有ai, bi合起来排序每点保留记号标明是a还是b,2nlog(2n)(还算O(nlogn)吧),然
: 后从头扫描到尾,碰到a计数加一,碰到b减一,假设计数最大的点在位置k,那么要找的点
: 就在k与k+1之间.
| | | h*****g
发帖数: 312 | 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).
| d*****y
发帖数: 205 | 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就算了
| C***U
发帖数: 2406 | 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就算了
| l*********8
发帖数: 4642 | 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 的大作中提到】
: 还是没懂，谁能给详细解释下？
: 最好给个例子
| h*****g
发帖数: 312 | 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].
| h****a
发帖数: 222 | 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].
| l*********8
发帖数: 4642 | 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
: .
| h*****g
发帖数: 312 | 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).
| d*****y
发帖数: 205 | 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就算了
| C***U
发帖数: 2406 | 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就算了
| | | l*********8
发帖数: 4642 | 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 的大作中提到】
: 还是没懂，谁能给详细解释下？
: 最好给个例子
| h*****g
发帖数: 312 | 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].
| h****a
发帖数: 222 | 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].
| l*********8
发帖数: 4642 | 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
: .
| P******r
发帖数: 842 | 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就算了
|
|
