基于Priority Query求解校园峰值在读人数的实现方案咨询

你的思路是完全可行的，这是典型的区间权重峰值计算场景，优先队列是该类问题的标准高效解法，时间复杂度为O(nlogn)，完全适配你的需求。

原双优先队列思路的实现逻辑 #

你提到的两个优先队列的方案可以按如下逻辑落地：

• 构建两个小顶堆：
  • 开始堆：优先级为课程开始时间，存储所有未处理的课程的开始时间、结束时间、上课人数
  • 结束堆：优先级为课程结束时间，存储所有已开课但未下课的课程的结束时间、上课人数
• 执行步骤：
  1. 将所有课程推入开始堆完成初始化
  2. 初始化当前在校人数、峰值人数、峰值时段三个变量
  3. 每次取出开始堆中最早开课的课程，先对比当前课程的开始时间与结束堆堆顶的下课时间：所有早于等于当前开课时间的课程均已下课，依次弹出并从当前在校人数中扣除对应人数
  4. 计算当前课程加入后的在校人数，若大于已记录的峰值则更新峰值和对应时段
  5. 将当前课程的下课时间、人数推入结束堆，在校人数累加对应课程人数
  6. 重复步骤3-5直到开始堆为空，最终输出峰值和时段即可

优化建议 #

方案1：简化为单优先队列+预排序（空间占用更低） #

不需要维护两个优先队列，只需提前将所有课程按开始时间升序排序，仅用一个结束堆存储已开课的结束信息即可，逻辑和双队列完全一致，仅减少了一个堆的维护开销，时间复杂度不变，示例代码如下：

import heapq

def calc_peak(courses):
    # courses输入格式：[(开始时间戳, 结束时间戳, 上课人数)]
    courses.sort()
    end_heap = []
    current = 0
    max_people = 0
    peak_start = 0
    peak_end = 0
    course_count = len(courses)

    for idx in range(course_count):
        s, e, cnt = courses[idx]
        # 先弹出所有已下课的课程
        while end_heap and end_heap[0][0] <= s:
            end_time, end_cnt = heapq.heappop(end_heap)
            current -= end_cnt
            # 检测下课事件后的时段峰值
            if current > max_people:
                max_people = current
                peak_start = end_time
                peak_end = s
        # 检测当前课程加入后的时段峰值
        next_event_time = end_heap[0][0] if end_heap else (courses[idx+1][0] if idx < course_count -1 else e)
        if current + cnt > max_people:
            max_people = current + cnt
            peak_start = s
            peak_end = min(next_event_time, e)
        # 加入当前课程
        heapq.heappush(end_heap, (e, cnt))
        current += cnt
    return max_people, peak_start, peak_end

# 用你给出的示例测试
test_courses = [
    (9*3600, 11*3600, 50),
    (10*3600, 12*3600, 25),
    (14*3600, 16*3600, 60),
    (17*3600, 18*3600, 70)
]
peak_num, ps, pe = calc_peak(test_courses)
print(f"峰值人数：{peak_num}，峰值时段：{ps//3600}:00-{pe//3600}:00")
# 输出结果：峰值人数：75，峰值时段：10:00-11:00，和示例计算结果完全匹配

方案2：小数据量场景可改用扫描线算法（逻辑更简单） #

如果单日课程数量小于100，完全可以用更易维护的扫描线方案，不需要优先队列：

1. 将所有课程拆为两个事件：开始事件（时间点，+人数）、结束事件（时间点，-人数）
2. 对所有事件按时间排序，时间相同的情况下结束事件排在开始事件前面（避免同时间点下课和上课的人数统计错误，比如11点下课的学生，11点已经不算在校）
3. 遍历所有事件累加人数，遍历过程中记录最大值即可

额外注意点 #

• 所有时间建议统一转换为秒/分钟级时间戳处理，避免字符串时间比较、时区等问题
• 如果需要统计多日峰值，按天拆分课程后分别计算即可

内容的提问来源于stack exchange，提问作者EricHom