运动会的竞赛日程管理

Question

某运动会设立N个比赛项目，每个运动员可以参加1-3个项目。试问如何安排比赛日程，既可以使，既可以使同一运动员参加的项目不在同一单位时间进行，又使总的竞赛日程最短。(用数据结构的队列解决问题)

Answer 1

问题抽象：若将此问题抽象成数学模型，则归属于“划分子集”问题。N个比赛项目构成一个大小为n的集合，有同一运动员参加的项目则抽象为“冲突”关系。

解决问题：假设某运动会设有9个项目，A = {0, 1, 2, 3, 4, 5, 6, 7, 8}，7名运动员报名参加的项目分别为：(1, 4, 8)、(1, 7)、(8, 3)、(1, 0, 5)、(3, 4)、(5, 6, 2)和(6, 4)，则构成一个冲突关系的集合R = { (1, 4), (4, 8), (1, 8), (1, 7), (8, 3), (1, 0), (0, 5), (1, 5), (3, 4), (5, 6), (5, 2), (6, 2), (6, 4)}（一对括号中的两个项目不能安排在同一单位时间）。“划分子集”问题即将集合A划分成k个互不相交的子集A1, A2, ... , Ak(k <= n)，使同一子集中的元素均无冲突关系。