清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.1活动安排问题 设有n个活动的集合E={1,2…,n,其中每个活动都要 求使用同一资源,如演讲会场等,而在同一时间内只有 个活动能使用这一资源。每个活动都有一个要求使用该资 源的起始时间si和一个结束时间f,且si<fi。如果选择了活 动,则它在半开时间区间[sf内占用资源。若区间[si,f) 与区间[Sj,f)不相交,则称活动与活动是相容的。也就是 说,当sif或jf时,活动与活动相容。5 4.1 活动安排问题 设有n个活动的集合E={1,2,…,n}，其中每个活动都要 求使用同一资源，如演讲会场等，而在同一时间内只有一 个活动能使用这一资源。每个活动i都有一个要求使用该资 源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活 动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi) 与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是 说，当si≥fj或sj≥fi时，活动i与活动j相容