p*******o
发帖数: 3564 | 1 今早在careercup上看到，http://www.careercup.com/question?id=12523672
Assume we have n people. Each one has a starting time and ending time. For
any people, set flag to true if his/her time range overlaps with anyone else
's.
假设完全没有排序，怎么搞O(N)算法，下面讨论中所谓的Hashtable bucket是什么意思
，如何实现 |
a******a
发帖数: 2646 | 2 应该有nlgn 算法
struct person
{ start time
end time
}
读入person
按start time binary排序，是 nlgn
如果重叠，修改
struct, 另
person.start =min
person.end =max
合并成为一个记录。 |
m*******l
发帖数: 12782 | 3 他要的是O(n)阿
【在 a******a 的大作中提到】
: 应该有nlgn 算法
: struct person
: { start time
: end time
: }
: 读入person
: 按start time binary排序，是 nlgn
: 如果重叠，修改
: struct, 另
: person.start =min
|
H****s
发帖数: 247 | 4 Step 1: Find the latest start time and the earliest finish time during the
first iteration.
Step 2:Compare each interval with the two numbers got from the first step
during the second iteration.
Two iterations with run time O(n)
【在 m*******l 的大作中提到】
: 他要的是O(n)阿
|
w***g
发帖数: 5958 | 5 我觉得没有O(N)的算法。
else
【在 p*******o 的大作中提到】
: 今早在careercup上看到，http://www.careercup.com/question?id=12523672
: Assume we have n people. Each one has a starting time and ending time. For
: any people, set flag to true if his/her time range overlaps with anyone else
: 's.
: 假设完全没有排序，怎么搞O(N)算法，下面讨论中所谓的Hashtable bucket是什么意思
: ，如何实现
|
p*****2
发帖数: 21240 | 6 如果只是时间的话，没有日期的话，那就是24个小时。如果计算到分钟的话，就是1440
分钟，那么定义这么一个数组。
int[] times=new int[1440];
第一遍扫描的时候如果一个人的start end time 包括这个分钟，就 times[i]++。
第二遍扫描的时候如果这个人的start-end time中有times[i]>1 就说明有overlap。 |
r****t
发帖数: 10904 | 7 整数排序
【在 w***g 的大作中提到】
: 我觉得没有O(N)的算法。
:
: else
|
p*****2
发帖数: 21240 | 8
bucket sort可以。先按分钟，再按小时。
【在 r****t 的大作中提到】
: 整数排序
|
r****t
发帖数: 10904 | 9 bucket radix sort? hoho
【在 p*****2 的大作中提到】
:
: bucket sort可以。先按分钟，再按小时。
|
z******w
发帖数: 36 | 10 嗯，radix sort排序后扫描一遍就可以求出overlap的元素了 |
