b**********5
发帖数: 7881 | |
a*****u
发帖数: 1712 | 2 应该是要用interval tree。不过如果其他常见题目还没准备好，可以先不专研这个，
有点太小众了 |
b**********5
发帖数: 7881 | 3 interval tree我知道， 但还是做不出less than O(n^2).
【在 a*****u 的大作中提到】
: 应该是要用interval tree。不过如果其他常见题目还没准备好，可以先不专研这个，
: 有点太小众了
|
c*****e
发帖数: 59 | 4 This is my solution.
first, sort the ids in terms of start time in ascending order
second, sort the ids in terms of end time in descending order
if the interval of one id_A falls into the interval of another id_B, then
the start time of id_A should be after that of id_B, and the end time of id_
B should be after that of id_A.
Therefore, we can use two loops to find out the number of ids that fall into
any given id by searching the ordered id sequences.
Time complexity is O(2log(n)+n^2) ~ O(n^2)
For the given example,
http://discuss.leetcode.com/questions/2274/count-number-of-over
Start time sequence: 1 2 5 4 3
End time sequence: 2 5 3 1 4
output:
3 0
4 0
1 1 //id 4 falls in id 1;
5 2 //id 3,4 fall in id 5;
2 3 //id 5,4,3 fall in id 2 |
b**********5
发帖数: 7881 | 5 人家是要小于n^2
id_
into
【在 c*****e 的大作中提到】
: This is my solution.
: first, sort the ids in terms of start time in ascending order
: second, sort the ids in terms of end time in descending order
: if the interval of one id_A falls into the interval of another id_B, then
: the start time of id_A should be after that of id_B, and the end time of id_
: B should be after that of id_A.
: Therefore, we can use two loops to find out the number of ids that fall into
: any given id by searching the ordered id sequences.
: Time complexity is O(2log(n)+n^2) ~ O(n^2)
: For the given example,
|
e*******8
发帖数: 94 | |
x***y
发帖数: 633 | 7 interval tree for sure O(nlogn). Check how interval tree gets log(n) time
for inertion and deletion. |
s****n
发帖数: 70 | 8 Not for sure...
如果用>表示包含关系，那么如果是这种情况
i1 > i2 > i3 > ... > in
用interval tree的话查询i1要遍历所有n个叶节点，查询i2要遍历至少n-1个节点。。
。以此类推，一共要访问O(n^2)叶节点。
【在 x***y 的大作中提到】
: interval tree for sure O(nlogn). Check how interval tree gets log(n) time
: for inertion and deletion.
|
e*******8
发帖数: 94 | 9 直接单用interval tree的确不行，但是这种partition tree一般好象都可以augment吧
（就是把解决reporting问题的data structure augment成解决counting问题的data
structure），不过我也没想清楚interval tree对这个问题应该怎么augment..
segment tree倒是可以用，但是又总觉得用segment tree＋fenwick tree有点杀鸡焉用
割牛刀的感觉...
【在 s****n 的大作中提到】
: Not for sure...
: 如果用>表示包含关系，那么如果是这种情况
: i1 > i2 > i3 > ... > in
: 用interval tree的话查询i1要遍历所有n个叶节点，查询i2要遍历至少n-1个节点。。
: 。以此类推，一共要访问O(n^2)叶节点。
|
