有n台打印机和m个请求，每个请求有开始时间和结束时间。一个请求可被分配给任意一台打印机，要求同一台打印机上任意两个请求的时间区间不能重叠（允许端点相接）。判断所有请求是否可以全部被分配。例如n=2时，请求[2,6]、[1,5]、[3,4]、[7,8]，前两个分别分配给两台打印机，[3,4]与两者冲突所以不可行，[7,8]可与[2,6]同机。请给出算法并分析复杂度。
考察说明
考察区间调度与贪心算法的应用及正确性判断
回答思路
- 能将问题转化为区间图着色或打印机空闲区间复用问题
- 提出正确算法，如按结束时间排序后贪心分配
- 能给出反例说明简单贪心的局限或正确证明
- 分析时间与空间复杂度
本题已收录答题指导
本题附完整参考答案与评分标准
登录后可查看结构化答题指导；也可以直接开一场模拟面试，AI 面试官用本题实时追问并给出评分。