区间划分算法

题目描述：给定一组区间和一个点，要求找出所有包含该点的区间。例如，给定区间集合 intervals = [[1,3], [2,6], [8,10], [15,18]] 和点 p = 2，算法应返回包含点2的所有区间，即 [[1,3], [2,6]]。

解题过程：

1. 问题分析：

   • 输入：一个区间列表（每个区间由起点和终点表示）和一个目标点p
   • 输出：所有包含点p的区间集合
   • 关键判断：一个区间[start, end]包含点p当且仅当 start ≤ p ≤ end

2. 暴力解法：

   • 遍历区间列表中的每个区间
   • 对每个区间检查是否满足 start ≤ p ≤ end
   • 将满足条件的区间加入结果集
   • 时间复杂度：O(n)，其中n为区间数量
   • 空间复杂度：O(k)，其中k为包含点p的区间数量

3. 优化思路（当需要多次查询时）：

   • 如果需要对同一个区间集合进行多次点查询，可以预先构建数据结构
   • 方法一：按区间起点排序，使用二分查找快速定位
   • 方法二：使用线段树或区间树等高级数据结构

4. 排序+二分查找优化：

   • 将区间按起点从小到大排序
   • 找到所有起点 ≤ p 的区间
   • 在这些区间中筛选出终点 ≥ p 的区间
   • 时间复杂度：预处理排序O(nlogn)，每次查询O(logn + m)，其中m为结果数量

5. 算法实现示例：

   def find_intervals_containing_point(intervals, p):
       result = []
       for interval in intervals:
           if interval[0] <= p <= interval[1]:
               result.append(interval)
       return result
   

6. 边界情况处理：

   • 空区间列表：返回空列表
   • 点p不在任何区间内：返回空列表
   • 区间为开区间或半开区间：根据具体问题调整判断条件

7. 应用场景：

   • 日程安排系统中查找特定时间点的所有活动
   • 地理信息系统中查询包含某个位置的所有区域
   • 数据库查询优化中的区间索引