排课系统
教授A: 最近我们学院的课程安排总是出问题，教师的时间冲突经常发生。你觉得我们可以引入排课软件来解决这个问题吗？
学生B: 当然可以！排课软件可以通过算法优化课程表，减少时间冲突。我之前做过一个小项目，可以用Python实现基本功能。
教授A: 那你能给我展示一下具体的代码吗？
学生B: 好的，首先我们需要定义一个课程类和教师类，存储基本信息。
class Course:
def __init__(self, name, teacher, time_slot):
self.name = name
self.teacher = teacher
self.time_slot = time_slot
class Teacher:
def __init__(self, name):
self.name = name
self.available_slots = set()
def add_availability(teacher, slot):
teacher.available_slots.add(slot)
教授A: 这样的话，我们就可以根据教师的可用时间段来安排课程了。
学生B: 是的，接下来我们需要设计一个简单的算法来匹配课程和教师的空闲时间。
def assign_courses(courses, teachers):
for course in courses:
for teacher in teachers:
if course.time_slot in teacher.available_slots:
teacher.available_slots.remove(course.time_slot)
course.teacher = teacher
break
教授A: 如果课程数量很多，这个算法会不会很慢？
学生B: 是的，目前的算法时间复杂度较高。我们可以使用图论中的二分图匹配算法来优化。
from collections import defaultdict
def bipartite_matching(graph):
pair_u = {}
pair_v = {}
def dfs(u):
for v in graph[u]:
if v not in pair_v or (v not in pair_u and dfs(pair_v[v])):
pair_u[v] = u
pair_v[u] = v
return True
return False
for u in graph:
if u not in pair_u:
dfs(u)
return len(pair_u)
教授A: 很棒！这样不仅提高了效率，还减少了手动调整的工作量。
学生B: 是的，未来我们还可以加入更多功能，比如自动调整冲突或生成多版本的课程表。
