刷题笔记合集🔗

人数最多的站点

问题描述

小毛的公园园区提供小火车单向通行，从园区站点编号最小到最大通行如12341，然后供员工在各个办公园区穿梭，通过对公司 个员工调研统计到每个员工的坐车区间，包含前后站点，请设计一个程序计算出小火车在哪个园区站点时人数最多。

输入格式

第 行，为调研员工人数。

第 行开始，为每个员工的上车站点和下车站点。
使用数字代替每个园区用空格分割，如 表示从第 个园区上车，在第 个园区下车。

输出格式

人数最多时的园区站点编号，最多人数相同时返回编号最小的园区站点。

样例输入

3
1 3
2 4
1 4

样例输出

2

数据范围

题解

这道题本质上是求解最大重叠区间问题的变种。我们需要找出在哪个站点上，同时有最多的员工乘坐小火车。

首先我们需要理解题目的关键点：小火车是按照从编号最小到最大的顺序单向通行的，比如从1到4，然后可能循环回1。这意味着员工的乘车区间可能有两种情况：

1. 上车站点编号小于下车站点，例如[1,3]表示从1站上车，3站下车
2. 上车站点编号大于下车站点，例如[3,2]表示从3站坐到4，再从1坐到2

对于第二种情况，我们需要将其拆分为两个区间：[3,4]和[1,2]，因为这是小火车的实际运行路线。

解题思路如下：

1. 将每个员工的乘车区间读入，如果上车站点大于下车站点，则拆分为两个区间
2. 对所有区间按照起始站点排序
3. 使用扫描线算法或者差分数组来统计每个站点的人数
4. 找出人数最多的站点，如果有多个，选择编号最小的

我选择使用扫描线算法结合小顶堆来解决这个问题：

• 将所有区间按照起始位置排序
• 遍历排序后的区间，维护一个小顶堆（存储区间的结束位置）
• 当我们遍历到一个新区间时，将小顶堆中所有结束位置小于当前区间起始位置的区间移除
• 此时小顶堆中剩余的区间数就是与当前区间重叠的区间数
• 记录最大重叠区间数和对应的起始位置

时间复杂度分析：

• 排序的时间复杂度为O(n log n)
• 每个区间最多被加入和移出堆一次，所以堆操作的时间复杂度也是O(n log n)
• 总体时间复杂度为O(n log n)，其中n为区间数量

这个算法对于给定的数据范围是高效的，即使员工数量很大也能快速得出结果。

参考代码

• Python

import sys
import heapq
input = lambda:sys.stdin.readline().strip()

# 读取输入
n = int(input())
ranges = []

# 读取每个员工的乘车区间
for _ in range(n):
    start, end = map(int, input().split())
    ranges.append([start, end])

# 找出全部站点中的最大站点编号
max_station = max(max(start, end) for start, end in ranges)

# 处理区间：如果起点大于终点，拆分为两个区间
processed_ranges = []
for start, end in ranges:
    if start <= end:
        processed_ranges.append([start, end])
    else:
        # 从起点到最大站点
        processed_ranges.append([start, max_station])
        # 从1到终点
        processed_ranges.append([1, end])

# 按起始站点排序
processed_ranges.sort(key=lambda x: x[0])

# 使用扫描线算法和小顶堆统计各站点人数
max_people = 0
result_station = 0
end_heap = []  # 小顶堆，存储区间结束位置

for interval in processed_ranges:
    start, end = interval
    
    # 移除已经离开的乘客
    while end_heap and end_heap[0] < start:
        heapq.heappop(end_heap)
    
    # 添加当前区间的结束位置
    heapq.heappush(end_heap, end)
    
    # 当前人数是堆的大小
    current_people = len(end_heap)
    
    # 更新最大人数和对应站点
    if current_people > max_people:
        max_people = current_people
        result_station = start
    elif current_people == max_people and start < result_station:
        result_station = start

print(result_station)

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<pair<int, int>> ranges(n);
    int max_station = 0;
    
    // 读取每个员工的乘车区间
    for (int i = 0; i < n; i++) {
        cin >> ranges[i].first >> ranges[i].second;