r******n
发帖数: 170 | 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 | l****3
发帖数: 150 | 2 当然直接选结束时间最早的那个啊,不然怎么叫贪心?
【在 r******n 的大作中提到】
: 一直没弄请怎么解这题，正好从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
|
|
