区间图着色问题

问题描述：给定一组区间，每个区间代表一个需要占用某个资源的活动，要求找到最少需要多少种资源（颜色），使得所有冲突的区间被分配到不同的资源上。两个区间冲突的定义是它们的交集非空。

解题过程：

1. 问题理解

   • 将每个区间视为一个节点，如果两个区间有重叠（冲突），则在它们之间连一条边，形成一个区间图
   • 问题转化为：用最少的颜色给图的节点着色，使得相邻节点颜色不同
   • 关键观察：区间图是完美图的一种，其色数等于最大团的大小

2. 关键思路

   • 将区间按开始时间排序
   • 问题等价于：在任何时刻，找出同时进行的最大区间数量
   • 这个最大重叠数就是所需的最少资源数

3. 算法步骤
   a. 数据预处理：

   • 提取所有区间的开始点和结束点
   • 为每个点标记类型（开始/结束）和时间戳

   b. 扫描线算法：

   • 创建时间点列表：每个区间贡献两个点（开始点、结束点）
   • 按时间排序，时间相同时结束点优先于开始点（避免重复计数）
   • 初始化计数器count = 0，max_count = 0

   c. 扫描过程：

   • 遍历排序后的时间点：
     • 遇到开始点：count++，更新max_count = max(max_count, count)
     • 遇到结束点：count--
   • 扫描完成后，max_count就是所需的最少资源数

4. 示例验证
   区间：[[1,4], [2,5], [3,6], [5,7]]

   时间点排序：

   • 开始1（+1）→ count=1, max_count=1
   • 开始2（+1）→ count=2, max_count=2
   • 开始3（+1）→ count=3, max_count=3
   • 结束4（-1）→ count=2
   • 结束5（-1）→ count=1
   • 开始5（+1）→ count=2
   • 结束6（-1）→ count=1
   • 结束7（-1）→ count=0

   最大同时活动数=3，∴需要3种资源。

5. 算法分析

   • 时间复杂度：O(n log n)，主要来自排序
   • 空间复杂度：O(n)，存储时间点
   • 正确性保证：通过扫描线精确统计每个时刻的活跃区间数

6. 扩展应用

   • 会议室安排：最少需要多少会议室
   • 航班调度：最少需要多少登机口
   • 课程安排：最少需要多少教室

这个算法巧妙地将区间着色问题转化为时间点扫描问题，通过简单的计数操作就得到了最优解。