1. 题目背景与需求分析
2026年拼多多春招开发岗笔试中的这道排课题目,主要考察应聘者对算法设计和数据结构应用的能力。题目描述虽然未给出具体细节,但从"排课"这一关键词可以推断,这很可能是一个涉及时间安排、资源分配或约束满足的经典算法问题。
在实际开发场景中,排课类问题广泛存在于教育管理系统、会议安排系统、生产调度系统等领域。这类问题通常需要处理以下核心要素:
- 课程/任务的总量
- 时间段的划分与限制
- 教师/资源的可用性约束
- 学生/参与者的选择限制
2. 问题建模与抽象化处理
2.1 输入参数分析
根据常见的排课问题模式,我们可以合理推测题目可能包含以下输入参数:
- 课程数量n
- 教师数量m
- 时间段集合T
- 课程-教师匹配关系矩阵
- 可能的其他约束条件(如课程先后顺序、教室容量等)
2.2 约束条件分类
排课问题的约束通常分为两类:
- 硬约束:必须满足的条件(如一个教师不能同时上两门课)
- 软约束:尽量满足的优化目标(如教师偏好时间段)
2.3 输出要求
合理的输出应该包含:
- 每门课分配的时间段
- 对应的授课教师
- 满足所有硬约束的可行解
3. 算法设计与选择
3.1 回溯算法方案
对于小规模排课问题,回溯算法是直接的选择:
def backtrack(course_idx, schedule): if course_idx == n: return True for teacher in available_teachers[course_idx]: for time in available_times[course_idx]: if not conflict(teacher, time, schedule): schedule[course_idx] = (teacher, time) if backtrack(course_idx+1, schedule): return True schedule[course_idx] = None return False时间复杂度分析:最坏情况下为O((m×t)^n),其中m是教师数,t是时间段数,n是课程数。
3.2 贪心算法优化
对于大规模问题,可以采用贪心策略:
- 按课程约束程度排序(约束多的优先安排)
- 为每门课选择最早可用的时间段和教师
public void greedySchedule() { courses.sort(Comparator.comparingInt(c -> -c.constraints.size())); for (Course c : courses) { for (Teacher t : c.availableTeachers) { for (TimeSlot slot : timeSlots) { if (isValidAssignment(c, t, slot)) { assign(c, t, slot); break; } } } } }3.3 图着色问题转化
将排课问题建模为图着色问题:
- 每门课程是一个顶点
- 有冲突的课程之间建立边
- 颜色代表时间段
vector<int> graphColoring(int V, vector<vector<int>>& adj) { vector<int> result(V, -1); result[0] = 0; vector<bool> available(V, false); for (int u = 1; u < V; u++) { for (auto i : adj[u]) if (result[i] != -1) available[result[i]] = true; int cr; for (cr = 0; cr < V; cr++) if (!available[cr]) break; result[u] = cr; fill(available.begin(), available.end(), false); } return result; }4. 代码实现与测试
4.1 Java完整实现
import java.util.*; public class CourseScheduler { static class Course { int id; List<Integer> teachers; List<Integer> conflicts; public Course(int id) { this.id = id; this.teachers = new ArrayList<>(); this.conflicts = new ArrayList<>(); } } public static int[] scheduleCourses(List<Course> courses, int teacherCount, int timeSlotCount) { int n = courses.size(); int[] assignment = new int[n]; Arrays.fill(assignment, -1); // 按约束程度排序 courses.sort((a, b) -> b.conflicts.size() - a.conflicts.size()); if (!backtrack(0, courses, assignment, teacherCount, timeSlotCount)) { return new int[0]; // 无解 } return assignment; } private static boolean backtrack(int idx, List<Course> courses, int[] assignment, int teacherCount, int timeSlotCount) { if (idx == courses.size()) return true; Course current = courses.get(idx); for (int t : current.teachers) { for (int ts = 0; ts < timeSlotCount; ts++) { if (isValid(idx, t, ts, courses, assignment)) { assignment[idx] = ts; if (backtrack(idx+1, courses, assignment, teacherCount, timeSlotCount)) { return true; } assignment[idx] = -1; } } } return false; } private static boolean isValid(int courseIdx, int teacher, int timeSlot, List<Course> courses, int[] assignment) { Course current = courses.get(courseIdx); // 检查教师是否可用 for (int i = 0; i < courseIdx; i++) { if (assignment[i] == timeSlot && courses.get(i).teachers.contains(teacher)) { return false; } } // 检查课程冲突 for (int conflictIdx : current.conflicts) { if (conflictIdx < courseIdx && assignment[conflictIdx] == timeSlot) { return false; } } return true; } }4.2 Python优化实现
def schedule_courses(courses, teacher_count, time_slot_count): n = len(courses) assignment = [-1] * n # 预处理:按约束程度排序 courses_sorted = sorted(enumerate(courses), key=lambda x: -len(x[1]['conflicts'])) original_indices = [i for i, _ in courses_sorted] sorted_courses = [c for _, c in courses_sorted] def backtrack(idx): if idx == n: return True current = sorted_courses[idx] for teacher in current['teachers']: for ts in range(time_slot_count): if is_valid(idx, teacher, ts): assignment[original_indices[idx]] = ts if backtrack(idx + 1): return True assignment[original_indices[idx]] = -1 return False def is_valid(idx, teacher, time_slot): current = sorted_courses[idx] # 检查教师冲突 for i in range(idx): if (assignment[original_indices[i]] == time_slot and teacher in sorted_courses[i]['teachers']): return False # 检查课程冲突 for conflict in current['conflicts']: orig_conflict_idx = courses.index(conflict) sorted_conflict_idx = next(i for i, (orig, _) in enumerate(courses_sorted) if orig == orig_conflict_idx) if sorted_conflict_idx < idx and assignment[orig_conflict_idx] == time_slot: return False return True if backtrack(0): return assignment return []4.3 C++高效实现
#include <vector> #include <algorithm> using namespace std; struct Course { int id; vector<int> teachers; vector<int> conflicts; }; bool backtrack(int idx, const vector<Course>& courses, vector<int>& assignment, int teacherCount, int timeSlotCount) { if (idx == courses.size()) return true; const Course& current = courses[idx]; for (int teacher : current.teachers) { for (int ts = 0; ts < timeSlotCount; ++ts) { bool valid = true; // 检查教师冲突 for (int i = 0; i < idx; ++i) { if (assignment[i] == ts) { const auto& teachers = courses[i].teachers; if (find(teachers.begin(), teachers.end(), teacher) != teachers.end()) { valid = false; break; } } } // 检查课程冲突 if (valid) { for (int conflictIdx : current.conflicts) { if (conflictIdx < idx && assignment[conflictIdx] == ts) { valid = false; break; } } } if (valid) { assignment[idx] = ts; if (backtrack(idx + 1, courses, assignment, teacherCount, timeSlotCount)) { return true; } assignment[idx] = -1; } } } return false; } vector<int> scheduleCourses(vector<Course>& courses, int teacherCount, int timeSlotCount) { // 按约束程度排序 sort(courses.begin(), courses.end(), [](const Course& a, const Course& b) { return a.conflicts.size() > b.conflicts.size(); }); vector<int> assignment(courses.size(), -1); if (backtrack(0, courses, assignment, teacherCount, timeSlotCount)) { return assignment; } return {}; }5. 复杂度分析与优化策略
5.1 时间复杂度对比
| 算法 | 最坏时间复杂度 | 适用场景 |
|---|---|---|
| 回溯 | O((m×t)^n) | 小规模问题(n<10) |
| 贪心 | O(n log n + n×m×t) | 快速近似解 |
| 图着色 | O(n^2) | 仅考虑课程冲突 |
5.2 空间复杂度分析
所有实现的空间复杂度主要为:
- 存储解向量:O(n)
- 递归栈深度:O(n)(回溯算法)
- 辅助数据结构:O(n+m+t)
5.3 实际优化技巧
- 预处理排序:将最难安排的课程优先处理
- 剪枝策略:在回溯过程中尽早发现无效路径
- 记忆化:缓存已计算的状态(适用于动态规划变种)
- 启发式选择:优先尝试最可能成功的选择
6. 测试用例设计
6.1 基础测试用例
# 简单案例:2门课,1位老师,2个时间段,无冲突 courses = [ {'teachers': [0], 'conflicts': []}, {'teachers': [0], 'conflicts': []} ] print(schedule_courses(courses, 1, 2)) # 预期输出如 [0, 1]6.2 冲突测试用例
// 3门课,2位老师,2个时间段,课程0和1冲突 List<Course> courses = new ArrayList<>(); Course c0 = new Course(0); c0.teachers.add(0); c0.conflicts.add(1); Course c1 = new Course(1); c1.teachers.add(1); c1.conflicts.add(0); Course c2 = new Course(2); c2.teachers.add(0); c2.teachers.add(1); courses.add(c0); courses.add(c1); courses.add(c2); int[] result = CourseScheduler.scheduleCourses(courses, 2, 2); // 可能输出如 [0, 1, 0] 或 [1, 0, 1]6.3 无解测试用例
// 2门课必须同时上,但只有1位老师 vector<Course> courses = { {0, {0}, {1}}, {1, {0}, {0}} }; auto result = scheduleCourses(courses, 1, 2); assert(result.empty()); // 应无解7. 边界条件处理
- 无课程情况:应返回空列表
- 无教师情况:直接判定无解
- 时间段不足:根据冲突情况可能仍有解
- 重复冲突:确保不会重复检查
- 教师无可用时间:提前终止相关分支
8. 实际工程中的扩展考虑
- 并行化处理:将回溯任务分配到多个线程
- 增量更新:当新增课程时尽量不影响已有安排
- 偏好权重:考虑教师和学生的时间偏好
- 可视化调试:输出排课结果的甘特图
- 持久化存储:将排课结果保存到数据库
9. 面试中的变种问题
面试官可能会基于这个问题提出以下变种:
- 如果增加教室约束怎么处理?
- 如何找到所有可能的排课方案而非一个?
- 如果某些约束可以违反,如何最小化违反数量?
- 如何处理动态变化的课程和教师列表?
- 如何设计API接口供其他系统调用?
10. 性能优化实战技巧
- 使用位运算表示时间段和教师可用性
- 实现前向检查(forward checking)减少搜索空间
- 采用最小剩余值(MRV)启发式选择下一个课程
- 对教师按可用时间段数量排序
- 实现冲突导向的回跳(conflict-directed backjumping)
# 使用位运算优化的冲突检查示例 def is_valid_bitmask(current_assignment, new_teacher, new_time): teacher_mask = 1 << new_teacher time_mask = 1 << new_time return (current_assignment['teachers'] & teacher_mask) == 0 and \ (current_assignment['times'] & time_mask) == 0