报个NSC EAD timeline.# EB23 - 劳工卡
b*5
1 楼
http://discuss.leetcode.com/questions/2274/count-number-of-over
less than O(n^2)
less than O(n^2)
w*2
2 楼
01-06-2016 485+765+131 (NSC)
02-09-2016 收到指纹预约
02-19-2016 打指纹
02-24-2016 765 New Card Is Being Produced
PD 03/2012
02-09-2016 收到指纹预约
02-19-2016 打指纹
02-24-2016 765 New Card Is Being Produced
PD 03/2012
a*u
3 楼
应该是要用interval tree。不过如果其他常见题目还没准备好，可以先不专研这个，
有点太小众了
有点太小众了
d*g
4 楼
恭喜！ 同NSC, 指纹打了一个月了，EAD还没有批，不知道是不是指纹出了问题。。。
好担心 D：
【在 w*****2 的大作中提到】
: 01-06-2016 485+765+131 (NSC)
: 02-09-2016 收到指纹预约
: 02-19-2016 打指纹
: 02-24-2016 765 New Card Is Being Produced
: PD 03/2012
好担心 D：
【在 w*****2 的大作中提到】
: 01-06-2016 485+765+131 (NSC)
: 02-09-2016 收到指纹预约
: 02-19-2016 打指纹
: 02-24-2016 765 New Card Is Being Produced
: PD 03/2012
b*5
5 楼
interval tree我知道， 但还是做不出less than O(n^2).
【在 a*****u 的大作中提到】
: 应该是要用interval tree。不过如果其他常见题目还没准备好，可以先不专研这个，
: 有点太小众了
【在 a*****u 的大作中提到】
: 应该是要用interval tree。不过如果其他常见题目还没准备好，可以先不专研这个，
: 有点太小众了
c*e
6 楼
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
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
7 楼
人家是要小于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,
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
8 楼
x*y
9 楼
interval tree for sure O(nlogn). Check how interval tree gets log(n) time
for inertion and deletion.
for inertion and deletion.
s*n
10 楼
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.
如果用>表示包含关系，那么如果是这种情况
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
11 楼
直接单用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)叶节点。
（就是把解决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)叶节点。
相关阅读
想不通为什么h4 ead会优先于140 eadI485 case 在状态显示 user defined error？？什么意思 (转载)what happens to EB3想到了h4 ead的一大妙用NIW要不要建个微信群来讨论我们关注的问题像我们这种持H1签证NIW排期到了的人及其家属，填写I-765表时第16项应该填写什么？有了EAD卡就可以开公司了吗?以前的W2 form找不到了怎么办？ (转载)下两个月VB会不会像上次eb2放水pattern一样H1B 去加拿大出差，然后直接回美国不用签证？有过reckless driving （misdemeanor) 如何填485表C1b？哭死，今年刚博士毕业工作，公司竟然给我办eb3!!!要半绿卡和renew h1b, wage determination啥意思【求助】版主版花我该在办个EB2 140吗？求助:如果I485/131/765一起交,要不要分别提交证明材料,还是可以交一份485一般都是自费递交的吗？【EB2 2015年四月第37绿】 EB2 TSC Green todayPERM终于批到2014/11了H1b 3年到期 后，再延3年 的I797的receipt number也贡献一个EAD RENEW的TIMELINE