a********n
发帖数: 369 | 1 假设知道一天之内n个events的开始时间和结束时间，怎样检测出一天内所有的时间
conflicts?就是同一时间有两个或者多个events，精确到分钟即可。Just get the number of conflicts for each event is OK.
我只能想到把每个events的开始和结束时间跟别的比较一下，但是很慢O(n^2)。或者就
是检测每个分钟内的事件数，这样一天24小时，就是O(24*60*n)，但是似乎一般每天不会有那么多events~
请大家指点，谢谢啊！ |
B*****t
发帖数: 335 | 2 sort+greedy
or hash
【在 a********n 的大作中提到】
: 假设知道一天之内n个events的开始时间和结束时间，怎样检测出一天内所有的时间
: conflicts?就是同一时间有两个或者多个events，精确到分钟即可。Just get the number of conflicts for each event is OK.
: 我只能想到把每个events的开始和结束时间跟别的比较一下，但是很慢O(n^2)。或者就
: 是检测每个分钟内的事件数，这样一天24小时，就是O(24*60*n)，但是似乎一般每天不会有那么多events~
: 请大家指点，谢谢啊！
|
r****o
发帖数: 1950 | 3 请问，这时间段(start..end)怎么hash啊？
【在 B*****t 的大作中提到】
: sort+greedy
: or hash
|
h**6
发帖数: 4160 | 4 根据开始时间排序，然后检测相邻两个事件是否重叠，重叠就用最后结束时间和下一个
事件开始时间继续检测。 |
x***y
发帖数: 633 | 5 Sort all the start and end time and scan over the result array while keeping
a count of how many events are active; when the count becomes 2, record the
time t1; and when the count become 1, record the time t2 and add the t2-t1
to the total time, and go on to the end of sorted array....
number of conflicts for each event is OK.
不会有那么多events~
【在 a********n 的大作中提到】
: 假设知道一天之内n个events的开始时间和结束时间，怎样检测出一天内所有的时间
: conflicts?就是同一时间有两个或者多个events，精确到分钟即可。Just get the number of conflicts for each event is OK.
: 我只能想到把每个events的开始和结束时间跟别的比较一下，但是很慢O(n^2)。或者就
: 是检测每个分钟内的事件数，这样一天24小时，就是O(24*60*n)，但是似乎一般每天不会有那么多events~
: 请大家指点，谢谢啊！
|
s******t
发帖数: 2374 | 6 如果 start和end都sort的话
那么，在每个单位时间里，比如一分钟，只需要比较当前这一分钟里面的start和那些
end有先后关系。
t1 t2 t3 t4 t5...
====|=======|========|=======|===
|____e1___|
|___e2___|
|__e3__|
|__e4_|
这样，排序时nlogn
比较在worse情况下 等于：分钟数*n*n |
g********d
发帖数: 43 | 7 Segment tree. O(n*logn)
number of conflicts for each event is OK.
不会有那么多events~
【在 a********n 的大作中提到】
: 假设知道一天之内n个events的开始时间和结束时间，怎样检测出一天内所有的时间
: conflicts?就是同一时间有两个或者多个events，精确到分钟即可。Just get the number of conflicts for each event is OK.
: 我只能想到把每个events的开始和结束时间跟别的比较一下，但是很慢O(n^2)。或者就
: 是检测每个分钟内的事件数，这样一天24小时，就是O(24*60*n)，但是似乎一般每天不会有那么多events~
: 请大家指点，谢谢啊！
|
g********d
发帖数: 43 | 8 这样会漏掉一些
A |-----------------|
B |-------|
C |---------|
按你的算法，B和C的overlap好像没计算在内
【在 h**6 的大作中提到】
: 根据开始时间排序，然后检测相邻两个事件是否重叠，重叠就用最后结束时间和下一个
: 事件开始时间继续检测。
|
