狗狗的表情# Joke - 肚皮舞运动
r*n
1 楼
一直没弄请怎么解这题，正好从topcoder tutorial上看到有相关讲解：
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
不过还是没太清楚，这个伪码里的J=1是怎么选出来的？是直接选结束时间最早的那个
事件吗？记得版上似乎有讨论过，不过没翻出来。哪位知道在哪里吗？
Let N denote the number of activities and
{I} the activity I ( 1 <= I <= N )
For each {I}, consider S[I] and F[I] its starting and finishing time
Sort the activities in the increasing order of their finishing time
- that is, for every I < J we must have F [I] <= F [J]
// A denotes the set of the activities that will be selected
A = {1}
// J denotes the last activity selected
J = 1
For I = 2 to N
// we can select activity 'I' only if the last activity
// selected has already been finished
If S [I] >= F [J]
// select activity 'I'
A = A + {I}
// Activity 'I' now becomes the last activity selected
J = I
Endif
Endfor
Return A
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
不过还是没太清楚，这个伪码里的J=1是怎么选出来的？是直接选结束时间最早的那个
事件吗？记得版上似乎有讨论过，不过没翻出来。哪位知道在哪里吗？
Let N denote the number of activities and
{I} the activity I ( 1 <= I <= N )
For each {I}, consider S[I] and F[I] its starting and finishing time
Sort the activities in the increasing order of their finishing time
- that is, for every I < J we must have F [I] <= F [J]
// A denotes the set of the activities that will be selected
A = {1}
// J denotes the last activity selected
J = 1
For I = 2 to N
// we can select activity 'I' only if the last activity
// selected has already been finished
If S [I] >= F [J]
// select activity 'I'
A = A + {I}
// Activity 'I' now becomes the last activity selected
J = I
Endif
Endfor
Return A
