活动选择问题 nS={12…n}为n项活动的集合 S和f分别表示活动开始和结束时间(1≤i≤n) 活动和活动相容当且仅当s≥f或S12f 相容 不相容 ■目标:求两两相容的最大活动集活动选择问题 ◼ S={1,2,…,n}为n项活动的集合 ◼ si和fi分别表示活动i开始和结束时间(1 ≤ i ≤ n) ◼ 活动i和活动j相容当且仅当si ≥ fj或sj ≥ fi ◼ 相容 ◼ 不相容 ◼ 目标：求两两相容的最大活动集 1 2 5 6