l*9
2 楼
有人做过这个题没有: 2个排序数组，数组1的元素是integer range， 例如 2-4， 5-9
。。。有start integer number，end interger number2个fields，按照先start
number排序，再end number排序，每个元素就是一个range。 第二个数组是integer
。 2个都是升序。 问找出第二个数组里面不在第一个数组所有range的所有元素
。。。有start integer number，end interger number2个fields，按照先start
number排序，再end number排序，每个元素就是一个range。 第二个数组是integer
。 2个都是升序。 问找出第二个数组里面不在第一个数组所有range的所有元素
s*y
3 楼
这个不错
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
d*k
4 楼
It can be solved by the 'classic' method.
There are three kinds of point:
1. The start points of an interval
2. The end points of an interval
3. The points in second array.
Put them into one array and sort it by increasing position. One detail: for
points with same position, use the order: type1 < type3 < type2
Iterate the sorted array and maintain on status: number of opening intervals
so far. Let's denote it as N.
Initially, N = 0.
For each point, if it's type1, let N = N + 1. If it's type2, Let N = N - 1.
If it's type3, that point is 'out of range' iff N is zero.
P.S.
In a Linux box and the CN input method is broken yet again....
There are three kinds of point:
1. The start points of an interval
2. The end points of an interval
3. The points in second array.
Put them into one array and sort it by increasing position. One detail: for
points with same position, use the order: type1 < type3 < type2
Iterate the sorted array and maintain on status: number of opening intervals
so far. Let's denote it as N.
Initially, N = 0.
For each point, if it's type1, let N = N + 1. If it's type2, Let N = N - 1.
If it's type3, that point is 'out of range' iff N is zero.
P.S.
In a Linux box and the CN input method is broken yet again....
N*7
5 楼
re
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
e*8
6 楼
这个就是plane sweep的方法。因为输入已经排好序了，所以时间复杂度是O（n），n是
第一个数列的大小＋第二个数列的大小
for
intervals
【在 d*k 的大作中提到】
: It can be solved by the 'classic' method.
: There are three kinds of point:
: 1. The start points of an interval
: 2. The end points of an interval
: 3. The points in second array.
: Put them into one array and sort it by increasing position. One detail: for
: points with same position, use the order: type1 < type3 < type2
: Iterate the sorted array and maintain on status: number of opening intervals
: so far. Let's denote it as N.
: Initially, N = 0.
第一个数列的大小＋第二个数列的大小
for
intervals
【在 d*k 的大作中提到】
: It can be solved by the 'classic' method.
: There are three kinds of point:
: 1. The start points of an interval
: 2. The end points of an interval
: 3. The points in second array.
: Put them into one array and sort it by increasing position. One detail: for
: points with same position, use the order: type1 < type3 < type2
: Iterate the sorted array and maintain on status: number of opening intervals
: so far. Let's denote it as N.
: Initially, N = 0.
k*n
7 楼
re
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
l*9
8 楼
谢谢回复， 将它们merge到一个array时，是不是还需要记录它们的type？比如 2start
, 4end, 5, 6start, 9end ...? 因为iterate merged的数组的时候还需要判断是哪种
类型的。
不知道leetcode上面有没有类似的题目？
for
intervals
【在 d*k 的大作中提到】
: It can be solved by the 'classic' method.
: There are three kinds of point:
: 1. The start points of an interval
: 2. The end points of an interval
: 3. The points in second array.
: Put them into one array and sort it by increasing position. One detail: for
: points with same position, use the order: type1 < type3 < type2
: Iterate the sorted array and maintain on status: number of opening intervals
: so far. Let's denote it as N.
: Initially, N = 0.
, 4end, 5, 6start, 9end ...? 因为iterate merged的数组的时候还需要判断是哪种
类型的。
不知道leetcode上面有没有类似的题目？
for
intervals
【在 d*k 的大作中提到】
: It can be solved by the 'classic' method.
: There are three kinds of point:
: 1. The start points of an interval
: 2. The end points of an interval
: 3. The points in second array.
: Put them into one array and sort it by increasing position. One detail: for
: points with same position, use the order: type1 < type3 < type2
: Iterate the sorted array and maintain on status: number of opening intervals
: so far. Let's denote it as N.
: Initially, N = 0.
h*o
9 楼
好几个回帖的，怎么没有给我包子的？
没包子给的，不准回帖！
没包子给的，不准回帖！
z*e
10 楼
现在一看到这种题，第一想法就是有没有dp解
f*g
11 楼
问题是这垃圾有啥好玩的？
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
d*k
12 楼
当然要记录类型。。。不是说了吗，排序的时候也得看类型。
leetcode好像有吧，记不清了。
2start
【在 l**********9 的大作中提到】
: 谢谢回复， 将它们merge到一个array时，是不是还需要记录它们的type？比如 2start
: , 4end, 5, 6start, 9end ...? 因为iterate merged的数组的时候还需要判断是哪种
: 类型的。
: 不知道leetcode上面有没有类似的题目？
:
: for
: intervals
leetcode好像有吧，记不清了。
2start
【在 l**********9 的大作中提到】
: 谢谢回复， 将它们merge到一个array时，是不是还需要记录它们的type？比如 2start
: , 4end, 5, 6start, 9end ...? 因为iterate merged的数组的时候还需要判断是哪种
: 类型的。
: 不知道leetcode上面有没有类似的题目？
:
: for
: intervals
s*u
13 楼
re
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
R*Z
14 楼
想确认一下我对题的理解是否有误，这题中数组1是以下哪种形式？
A: {[start1, end1], [start2, end2]， ...}
B: {start1, start2, ..., end1, end2， ...}
-9
integer
【在 l**********9 的大作中提到】
: 有人做过这个题没有: 2个排序数组，数组1的元素是integer range， 例如 2-4， 5-9
: 。。。有start integer number，end interger number2个fields，按照先start
: number排序，再end number排序，每个元素就是一个range。 第二个数组是integer
: 。 2个都是升序。 问找出第二个数组里面不在第一个数组所有range的所有元素
A: {[start1, end1], [start2, end2]， ...}
B: {start1, start2, ..., end1, end2， ...}
-9
integer
【在 l**********9 的大作中提到】
: 有人做过这个题没有: 2个排序数组，数组1的元素是integer range， 例如 2-4， 5-9
: 。。。有start integer number，end interger number2个fields，按照先start
: number排序，再end number排序，每个元素就是一个range。 第二个数组是integer
: 。 2个都是升序。 问找出第二个数组里面不在第一个数组所有range的所有元素
w*4
15 楼
的确
说的有点道理
明天in 几台玩玩
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
说的有点道理
明天in 几台玩玩
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
s*p
16 楼
When you merge and sort, that can take O(nlogn), right? It is not linear
time algorithm.
for
intervals
【在 d*k 的大作中提到】
: It can be solved by the 'classic' method.
: There are three kinds of point:
: 1. The start points of an interval
: 2. The end points of an interval
: 3. The points in second array.
: Put them into one array and sort it by increasing position. One detail: for
: points with same position, use the order: type1 < type3 < type2
: Iterate the sorted array and maintain on status: number of opening intervals
: so far. Let's denote it as N.
: Initially, N = 0.
time algorithm.
for
intervals
【在 d*k 的大作中提到】
: It can be solved by the 'classic' method.
: There are three kinds of point:
: 1. The start points of an interval
: 2. The end points of an interval
: 3. The points in second array.
: Put them into one array and sort it by increasing position. One detail: for
: points with same position, use the order: type1 < type3 < type2
: Iterate the sorted array and maintain on status: number of opening intervals
: so far. Let's denote it as N.
: Initially, N = 0.
C*t
17 楼
RE
【在 h****o 的大作中提到】
: 好几个回帖的，怎么没有给我包子的？
: 没包子给的，不准回帖！
【在 h****o 的大作中提到】
: 好几个回帖的，怎么没有给我包子的？
: 没包子给的，不准回帖！
e*8
18 楼
不用直接排序啊（因为题目是说已经排好序之后怎么做）。不知道这步按照结束时间排
序是做什么，觉得好象没必要？要是可以单按照start time一个一个处理每个range，
我觉得算法
就是leetcode上的jump game ＋ merge sort中merge两个排好序的数组。
【在 s****p 的大作中提到】
: When you merge and sort, that can take O(nlogn), right? It is not linear
: time algorithm.
:
: for
: intervals
序是做什么，觉得好象没必要？要是可以单按照start time一个一个处理每个range，
我觉得算法
就是leetcode上的jump game ＋ merge sort中merge两个排好序的数组。
【在 s****p 的大作中提到】
: When you merge and sort, that can take O(nlogn), right? It is not linear
: time algorithm.
:
: for
: intervals
L*i
19 楼
re
s*w
20 楼
用 hashtable 应该是最好理解的了
for interval in array 1:
for value in interval:
hashtable.insert(value)
for int in array 2:
if hashtable.count(int)==0:
output
唯一的缺点是第二行可能比较慢，看共有多少 unique value
-9
integer
【在 l**********9 的大作中提到】
: 有人做过这个题没有: 2个排序数组，数组1的元素是integer range， 例如 2-4， 5-9
: 。。。有start integer number，end interger number2个fields，按照先start
: number排序，再end number排序，每个元素就是一个range。 第二个数组是integer
: 。 2个都是升序。 问找出第二个数组里面不在第一个数组所有range的所有元素
for interval in array 1:
for value in interval:
hashtable.insert(value)
for int in array 2:
if hashtable.count(int)==0:
output
唯一的缺点是第二行可能比较慢，看共有多少 unique value
-9
integer
【在 l**********9 的大作中提到】
: 有人做过这个题没有: 2个排序数组，数组1的元素是integer range， 例如 2-4， 5-9
: 。。。有start integer number，end interger number2个fields，按照先start
: number排序，再end number排序，每个元素就是一个range。 第二个数组是integer
: 。 2个都是升序。 问找出第二个数组里面不在第一个数组所有range的所有元素
a*e
21 楼
有道理哈
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
s*p
22 楼
Array 1 is sorted by range, if r1 < r2, it could be that r1.upper > r2.lower
. So when you merge lower and upper into the same array, it still need to be
sorted.
【在 e*******8 的大作中提到】
: 不用直接排序啊（因为题目是说已经排好序之后怎么做）。不知道这步按照结束时间排
: 序是做什么，觉得好象没必要？要是可以单按照start time一个一个处理每个range，
: 我觉得算法
: 就是leetcode上的jump game ＋ merge sort中merge两个排好序的数组。
. So when you merge lower and upper into the same array, it still need to be
sorted.
【在 e*******8 的大作中提到】
: 不用直接排序啊（因为题目是说已经排好序之后怎么做）。不知道这步按照结束时间排
: 序是做什么，觉得好象没必要？要是可以单按照start time一个一个处理每个range，
: 我觉得算法
: 就是leetcode上的jump game ＋ merge sort中merge两个排好序的数组。
a*k
23 楼
吃。。。
p*2
24 楼
如果把第一个merge的话是O(n), 然后找的话就是O(logn)了吧？
a*k
25 楼
Thx
e*8
26 楼
所以我才觉得不用按照finish time排序呀：要是单按照start time排序， events就只
是第一个array里的start time和第二个array里的点：依此扫描每个events （用merge
sort里merge两个sorted array的方法）：如果是start time，就检查是否可以向右扩
展被intervals覆盖的范围，然后相应的更新最大可以覆盖的范围；如果是第二个array
里的点，就检查是不是在当前被覆盖的范围内。
比如如果输入是［１，４］， ［２，５］， ［７，９］，［８，１０］，第二个
array的点是５，６，那么：
第一个event at １：当前覆盖的范围是［１，４］
第二个event at ２：当前覆盖的范围是［１，５］
第三个event at ５：５被覆盖
第四个event at ６：６没有被覆盖；
第五个event at ７：当前覆盖的范围是［７，９］
第六个event at ８：当前覆盖的范围是 ［７，１０］
最后输出是{6}。
是第一个array里的start time和第二个array里的点：依此扫描每个events （用merge
sort里merge两个sorted array的方法）：如果是start time，就检查是否可以向右扩
展被intervals覆盖的范围，然后相应的更新最大可以覆盖的范围；如果是第二个array
里的点，就检查是不是在当前被覆盖的范围内。
比如如果输入是［１，４］， ［２，５］， ［７，９］，［８，１０］，第二个
array的点是５，６，那么：
第一个event at １：当前覆盖的范围是［１，４］
第二个event at ２：当前覆盖的范围是［１，５］
第三个event at ５：５被覆盖
第四个event at ６：６没有被覆盖；
第五个event at ７：当前覆盖的范围是［７，９］
第六个event at ８：当前覆盖的范围是 ［７，１０］
最后输出是{6}。
d*r
27 楼
re baozi
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
r*n
28 楼
这种题目一看就知道对方想考察的是binary search的变体
描述算法比较verbose，这里给个例子
interval array A: [{1, 3}, {3, 4}, {7, 12}, {9, 10}] //按照[1, 3, 7, 9]来排
的顺
integer array B: [4, 5, 10]
1. binary search (actually upper_bound) B[0] = 4 in A: get i = 2 （if A[i]==
4，then ++i）
2. iterate through A[0, ..., i-1] until you find the first index j such that
its end time is >= 4: j = 1
3. because j < i, 4 is contained in an interval
4. binary search B[1] = 5 in A: get i = 2
5. iterate through A[j, ..., i-1] (j = 1) until you find the first index
such that its end time is >= 5: j = 2
6. because j == i, 5 is not contained in an interval
7. binary search B[2] = 10 in A: get i = 4
8. iterate through A[j, ..., i-1] (here j = 2)...... end time is >= 10: j =
2
9. because j < i, 10 is contained in A
because j is non-decreasing, iteration step (above 2, 5, 8) takes O(n), each
binary search takes O(logn), total running time is O(nlogn)
描述算法比较verbose，这里给个例子
interval array A: [{1, 3}, {3, 4}, {7, 12}, {9, 10}] //按照[1, 3, 7, 9]来排
的顺
integer array B: [4, 5, 10]
1. binary search (actually upper_bound) B[0] = 4 in A: get i = 2 （if A[i]==
4，then ++i）
2. iterate through A[0, ..., i-1] until you find the first index j such that
its end time is >= 4: j = 1
3. because j < i, 4 is contained in an interval
4. binary search B[1] = 5 in A: get i = 2
5. iterate through A[j, ..., i-1] (j = 1) until you find the first index
such that its end time is >= 5: j = 2
6. because j == i, 5 is not contained in an interval
7. binary search B[2] = 10 in A: get i = 4
8. iterate through A[j, ..., i-1] (here j = 2)...... end time is >= 10: j =
2
9. because j < i, 10 is contained in A
because j is non-decreasing, iteration step (above 2, 5, 8) takes O(n), each
binary search takes O(logn), total running time is O(nlogn)
s*t
29 楼
有道理，我的100多台ipad啊，我要call back
原出售价+5块，全部给我回来
老子铺地上睡觉
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
原出售价+5块，全部给我回来
老子铺地上睡觉
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
c*p
30 楼
先mark
a*e
31 楼
re
X*I
32 楼
I opened one. pretty cool. but I wish it could do multi-task
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
t*c
33 楼
re
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
【在 h****o 的大作中提到】
: 别不舍的，谁知道2012地球是不是打算恢复出厂设置
: 回帖的发包子撒
f*r
34 楼
re
l*n
35 楼
re
c*a
36 楼
re
相关阅读
P家面经Bloomberg面试题 兼问在纽约工作舒服吗？Amazon salary range for Fresh PhDbloomberg的onsite是全coding的问题吗申请的group leader发面试通知的时候变成了staff职位两个offer应该选哪个? Trulia vs Tumblr探讨：这几个IT大公司，对你吸引力排名？Business Analyst/Project manager Opening要不要follow up啊？is there a facebook R&D or facebook research (labs)?发offer的方式能看出来salary negociation的空间？帮国内朋友问H1毁约的后果讨论几道M家的题闹心！马上On-site，问个关于工作经历填表的事情Amazon AWS招人Database software engineer position available immediately (Atlanta)辞职一般都是周五么？100000FLC Data Center怎么查PhD 的工资？CV里读研时期的研究工作地点可以就写Dept. of xxx吗？