当前位置： 面试刷题>> 安排课程 (经典算法题500道)
### 完整题目描述
**题目：码小课课程安排**
码小课网站计划在一个学期内为学生们安排一系列编程课程。每门课程有不同的持续时间（以周为单位），并且部分课程之间存在先修关系，即学生必须先完成某些课程，才能开始其他课程的学习。请设计一个算法，以确定是否存在一种安排方式，使得所有课程都能在给定的学期内（假设学期足够长，足以容纳所有课程）被完成，同时满足所有课程的先修关系。
**输入**：
1. 课程列表，每门课程包含课程ID、课程名称和持续时间（周数）。
2. 先修关系列表，表示哪些课程是其他课程的先修课程。
**输出**：
- 如果存在满足条件的课程安排，输出一个可能的课程安排顺序（不需要是唯一的）。
- 如果不存在满足条件的课程安排，输出"无法安排所有课程"。
### 示例
**输入**：
```json
{
"courses": [
{"id": 1, "name": "编程基础", "duration": 6},
{"id": 2, "name": "数据结构与算法", "duration": 8, "prerequisites": [1]},
{"id": 3, "name": "Web开发基础", "duration": 4},
{"id": 4, "name": "高级Web开发", "duration": 10, "prerequisites": [3]},
{"id": 5, "name": "数据库原理", "duration": 7, "prerequisites": [1]}
]
}
```
**输出**：
```
1: 编程基础
3: Web开发基础
5: 数据库原理
2: 数据结构与算法
4: 高级Web开发
```
### PHP 示例代码
```php
$degree) {
if ($degree == 0) {
$queue[] = $id;
}
}
// 拓扑排序
while (!empty($queue)) {
$current = array_shift($queue);
$result[] = $current;
if (isset($graph[$current])) {
foreach ($graph[$current] as $neighbor) {
$inDegree[$neighbor]--;
if ($inDegree[$neighbor] == 0) {
$queue[] = $neighbor;
}
}
}
}
// 检查是否所有课程都被排序
if (count($result) != count($courses)) {
return "无法安排所有课程";
}
// 转换为课程名称
$sortedCourses = [];
foreach ($result as $id) {
foreach ($courses as $course) {
if ($course['id'] == $id) {
$sortedCourses[] = $course['name'];
break;
}
}
}
return implode("\n", array_map(function($name, $index) use ($sortedCourses) {
return "$index+1: $name";
}, $sortedCourses, array_keys($sortedCourses)));
}
// 示例输入
$courses = [
["id" => 1, "name" => "编程基础", "duration" => 6],
["id" => 2, "name" => "数据结构与算法", "duration" => 8, "prerequisites" => [1]],
["id" => 3, "name" => "Web开发基础", "duration" => 4],
["id" => 4, "name" => "高级Web开发", "duration" => 10, "prerequisites" => [3]],
["id" => 5, "name" => "数据库原理", "duration" => 7, "prerequisites" => [1]]
];
echo topologicalSort($courses);
?>
```
注意：此PHP代码仅处理了课程安排的逻辑部分，没有涉及学期时间长度是否足够的具体检查，因为题目已假设学期足够长。