解题思路

这是一道差分数组应用题，主要思路如下：

  1. 问题分析：

    • 条火车路线，每条路线从 站到 站
    • 火车在起点和终点之间的所有站点都会停靠
    • 需要计算同时运营的最大路线数量
    • 即求最大重叠区间数

  2. 解决方案：

    • 使用差分数组统计区间覆盖
    • 对每个区间 ，在 处 ，在 处
    • 遍历差分数组的前缀和，得到每个位置的覆盖数
    • 记录最大覆盖数

  3. 实现细节：

    • 使用数组记录差分
    • 动态维护区间最大值
    • 注意数组范围

代码

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

const int N = 1e5 + 1;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    vector<int> diff(N, 0);  // 差分数组
    int xlimit = 0;
    
    // 读入区间并标记差分
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        xlimit = max(xlimit, y);
        diff[x]++;      // 起点增加1
        diff[y]--;      // 终点减少1
    }
    
    // 计算最大重叠区间
    int maxCount = 0, sum = 0;
    for (int i = 1; i <= xlimit; ++i) {
        sum += diff[i];  // 计算前缀和
        maxCount = max(maxCount, sum);
    }
    
    cout << maxCount << endl;
    return 0;
}

import java.util.*;

public class Main {
    static final int N = 100001;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] diff = new int[N];  // 差分数组
        int xlimit = 0;
        
        // 读入区间并标记差分
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            xlimit = Math.max(xlimit, y);
            diff[x]++;      // 起点增加1
            diff[y]--;      // 终点减少1
        }
        
        // 计算最大重叠区间
        int maxCount = 0, sum = 0;
        for (int i = 1; i <= xlimit; i++) {
            sum += diff[i];  // 计算前缀和
            maxCount = Math.max(maxCount, sum);
        }
        
        System.out.println(maxCount);
        sc.close();
    }
}

def solve():
    n = int(input())
    
    # 使用字典优化空间
    diff = {}  # 差分字典
    xlimit = 0
    
    # 读入区间并标记差分
    for _ in range(n):
        x, y = map(int, input().split())
        xlimit = max(xlimit, y)
        diff[x] = diff.get(x, 0) + 1  # 起点增加1
        diff[y] = diff.get(y, 0) - 1  # 终点减少1
    
    # 计算最大重叠区间
    max_count = curr_sum = 0
    for i in range(1, xlimit + 1):
        curr_sum += diff.get(i, 0)  # 计算前缀和
        max_count = max(max_count, curr_sum)
    
    return max_count

def main():
    print(solve())

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：差分数组
  • 时间复杂度： - 为路线数， 为最大站点编号
  • 空间复杂度： - 为最大站点编号