h*****g
发帖数: 944 | 1 说现在有一个array的activity, 每个activity都有自己的start time和 end time,
找出所有 至少与一个acticity conflict的activity
有什么比较efficient的办法吗？ |
b*******8
发帖数: 37364 | 2 先按开始时间排序nlogn，再扫一遍碰见重叠就完成了。O(nlogn)，如果已经排序好了
那就是O(n)。 |
c**y
发帖数: 172 | 3 你能解释一下如何
“再扫一遍碰见重叠就完成了”?
【在 b*******8 的大作中提到】
: 先按开始时间排序nlogn，再扫一遍碰见重叠就完成了。O(nlogn)，如果已经排序好了
: 那就是O(n)。
|
l*********r
发帖数: 674 | 4 按开始时间s1, s2, ... 排序，同时标记结束时间e1, e2, ...
扫第二遍的时候，如果没有conflict，应该是s1, e1, s2, e2, ...
如果有si, s_(i+1)连在一起那就是conflict
【在 c**y 的大作中提到】
: 你能解释一下如何
: “再扫一遍碰见重叠就完成了”?
|
h**********d
发帖数: 4313 | 5 这样只能判断是否有 conflict吧，如果要找出来，好像这样只能找到连续pair的重叠
，如果不连续但有重叠怎么办呢
【在 l*********r 的大作中提到】
: 按开始时间s1, s2, ... 排序，同时标记结束时间e1, e2, ...
: 扫第二遍的时候，如果没有conflict，应该是s1, e1, s2, e2, ...
: 如果有si, s_(i+1)连在一起那就是conflict
|
b*******8
发帖数: 37364 | 6 设按开始时间排序好以后是S1～Sn，对应的结束时间是E1~En(这个不一定Sorted）。那么只要依次比较E1~S2，E2~S3， ...， En-1~Sn，如果Si
【在 h**********d 的大作中提到】
: 这样只能判断是否有 conflict吧，如果要找出来，好像这样只能找到连续pair的重叠
: ，如果不连续但有重叠怎么办呢
|
h*****g
发帖数: 944 | 7 这样的complexity不就是N*N了吗？？
那么只要依次比较E1~S2，E2~S3， ...， En-1~Sn，如果Si
相冲突，这俩个同时加入输出。假设你要的输出是Activities的集合，而不是两两配对
的集合。
【在 b*******8 的大作中提到】
: 设按开始时间排序好以后是S1～Sn，对应的结束时间是E1~En(这个不一定Sorted）。那么只要依次比较E1~S2，E2~S3， ...， En-1~Sn，如果Si
|
h**********d
发帖数: 4313 | 8 如果第一个act包含了其他所有acts，其他acts之间没有冲突，这样只能输入头两个，
按题目应该输出所有吧
那么只要依次比较E1~S2，E2~S3， ...， En-1~Sn，如果Si
相冲突，这俩个同时加入输出。假设你要的输出是Activities的集合，而不是两两配对
的集合。
【在 b*******8 的大作中提到】
: 设按开始时间排序好以后是S1～Sn，对应的结束时间是E1~En(这个不一定Sorted）。那么只要依次比较E1~S2，E2~S3， ...， En-1~Sn，如果Si
|
h*****g
发帖数: 944 | 9 对啊，需要输出所有的，大家有答案吗？
【在 h**********d 的大作中提到】
: 如果第一个act包含了其他所有acts，其他acts之间没有冲突，这样只能输入头两个，
: 按题目应该输出所有吧
:
: 那么只要依次比较E1~S2，E2~S3， ...， En-1~Sn，如果Si: 相冲突，这俩个同时加入输出。假设你要的输出是Activities的集合，而不是两两配对
: 的集合。
|
p*****e
发帖数: 53 | 10 开始和结束的时间都同意参加排队，然后找overlap就可以了吧
【在 h*****g 的大作中提到】
: 对啊，需要输出所有的，大家有答案吗？
|
e********s
发帖数: 248 | 11 1. 开始和结束的时间一起排序
2. 用一个stack来chek overlap
3. 可能要用一个array或者hash table来uniquefy results.
【在 p*****e 的大作中提到】
: 开始和结束的时间都同意参加排队，然后找overlap就可以了吧
|
