华为OD机试 2024E卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
公园园区提供小火车单向通行，从园区站点编号最小到最大通行（如1→2→3→4→1），然后供员工在各个办公园区穿梭。通过对公司N个员工调研统计到每个员工的坐车区间，包含前后站点，请设计一个程序计算出小火车在哪个园区站点时人数最多。
二、输入描述
第1行：为调研员工人数。
第2行开始：为每个员工的上车站点和下车站点。
使用数字代表每个园区且为整数分割，如3表示从第3个园区上车，在第5个园区下车。
三、输出描述
人数最多时的园区站点编号，最多人数同时出现在的园区站点最小的园区站点。
四、测试用例
测试用例1：
1、输入
3
1 3
2 4
3 1
2、输出
3
3、说明
测试用例2：
1、输入
5
2 5
3 6
1 4
5 2
4 1
2、输出
4
3、说明
五、解题思路
我们需要找出在小火车经过的所有园区站点中，乘客数量最多的站点编号。为了高效计算每个站点的乘客数量，可以采用差分数组和前缀和的方法。
- 输入处理：首先读取员工人数N，然后读取每位员工的上车站点和下车站点。
- 确定最大站点编号：遍历所有上车和下车站点，找出最大的站点编号M，以便初始化差分数组。
- 差分数组初始化：创建一个长度为M+2的差分数组，用于记录每个站点乘客数量的变化。
- 处理每位员工的乘车区间：
- 如果上车站点 ≤ 下车站点，表示乘客在区间内直行，不涉及环形绕行。
- 在上车站点位置增加1，在下车站点的下一个位置减少1。
- 如果上车站点 > 下车站点，表示乘客需要绕行一圈。
- 在上车站点位置增加1，在最大站点的下一个位置减少1。
- 在第1站点位置增加1，在下车站点的下一个位置减少1。
- 计算前缀和：通过遍历差分数组，累加得到每个站点的实际乘客数量。
- 找出最大乘客数量的站点：遍历前缀和数组，记录乘客数量最多的站点编号，若有多个站点数量相同，则选择编号最小的站点。
六、Python算法源码
# 导入所需模块
import sysdef main():# 创建一个读取输入的迭代器input = sys.stdin.read().split()it = iter(input)# 读取员工人数N = int(next(it))# 初始化区间列表和最大站点编号intervals = []maxStation = 0# 读取每位员工的上车和下车站点，并更新最大站点编号for _ in range(N):start = int(next(it)) # 上车站点end = int(next(it)) # 下车站点intervals.append((start, end))if start > maxStation:maxStation = startif end > maxStation:maxStation = end# 初始化差分数组，长度为最大站点编号加2diff = [0] * (maxStation + 2)# 处理每位员工的乘车区间for start, end in intervals:if start <= end:# 区间不绕行，直接增加和减少对应位置diff[start] += 1diff[end + 1] -= 1else:# 区间绕行一圈，分两部分处理diff[start] += 1diff[maxStation + 1] -= 1diff[1] += 1diff[end + 1] -= 1# 计算前缀和，找到最大乘客数量和对应的最小站点编号maxCount = 0resultStation = 1current = 0for i in range(1, maxStation + 1):current += diff[i]if current > maxCount:maxCount = currentresultStation = i# 输出结果print(resultStation)# 调用主函数
if __name__ == "__main__":main()七、JavaScript算法源码
// 读取标准输入并处理
const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let input = [];
rl.on('line', function(line) {input = input.concat(line.trim().split(/\s+/));
}).on('close', function() {// 创建输入的迭代器let it = input[Symbol.iterator]();// 读取员工人数let N = parseInt(it.next().value);// 初始化区间列表和最大站点编号let intervals = [];let maxStation = 0;// 读取每位员工的上车和下车站点，并更新最大站点编号for(let i = 0; i < N; i++) {let start = parseInt(it.next().value); // 上车站点let end = parseInt(it.next().value); // 下车站点intervals.push([start, end]);if(start > maxStation) maxStation = start;if(end > maxStation) maxStation = end;}// 初始化差分数组，长度为最大站点编号加2let diff = new Array(maxStation + 2).fill(0);// 处理每位员工的乘车区间intervals.forEach(([start, end]) => {if(start <= end){// 区间不绕行，直接增加和减少对应位置diff[start] += 1;diff[end + 1] -= 1;} else {// 区间绕行一圈，分两部分处理diff[start] += 1;diff[maxStation + 1] -= 1;diff[1] += 1;diff[end + 1] -= 1;}});// 计算前缀和，找到最大乘客数量和对应的最小站点编号let maxCount = 0;let resultStation = 1;let current = 0;for(let i = 1; i <= maxStation; i++){current += diff[i];if(current > maxCount){maxCount = current;resultStation = i;}}// 输出结果console.log(resultStation);
});八、C算法源码
#include <stdio.h>
#include <stdlib.h>int main(){int N;// 读取员工人数scanf("%d", &N);// 动态分配区间数组int (*intervals)[2] = malloc(N * sizeof(*intervals));if(intervals == NULL){return 1; // 内存分配失败}int maxStation = 0;// 读取每位员工的上车和下车站点，并更新最大站点编号for(int i = 0; i < N; i++){scanf("%d %d", &intervals[i][0], &intervals[i][1]);if(intervals[i][0] > maxStation){maxStation = intervals[i][0];}if(intervals[i][1] > maxStation){maxStation = intervals[i][1];}}// 动态分配差分数组，初始化为0int *diff = calloc(maxStation + 2, sizeof(int));if(diff == NULL){free(intervals);return 1; // 内存分配失败}// 处理每位员工的乘车区间for(int i = 0; i < N; i++){int start = intervals[i][0];int end = intervals[i][1];if(start <= end){// 区间不绕行，直接增加和减少对应位置diff[start] += 1;diff[end + 1] -= 1;}else{// 区间绕行一圈，分两部分处理diff[start] += 1;diff[maxStation + 1] -= 1;diff[1] += 1;diff[end + 1] -= 1;}}// 计算前缀和，找到最大乘客数量和对应的最小站点编号int maxCount = 0;int resultStation = 1;int current = 0;for(int i = 1; i <= maxStation; i++){current += diff[i];if(current > maxCount){maxCount = current;resultStation = i;}}// 输出结果printf("%d\n", resultStation);// 释放动态分配的内存free(intervals);free(diff);return 0;
}九、C++算法源码
#include <iostream>
#include <vector>
using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(0);int N;// 读取员工人数cin >> N;// 初始化区间列表和最大站点编号vector<pair<int, int>> intervals(N);int maxStation = 0;// 读取每位员工的上车和下车站点，并更新最大站点编号for(int i = 0; i < N; i++){cin >> intervals[i].first >> intervals[i].second;if(intervals[i].first > maxStation){maxStation = intervals[i].first;}if(intervals[i].second > maxStation){maxStation = intervals[i].second;}}// 初始化差分数组，长度为最大站点编号加2，并初始化为0vector<int> diff(maxStation + 2, 0);// 处理每位员工的乘车区间for(auto &[start, end] : intervals){if(start <= end){// 区间不绕行，直接增加和减少对应位置diff[start] += 1;diff[end + 1] -= 1;}else{// 区间绕行一圈，分两部分处理diff[start] += 1;diff[maxStation + 1] -= 1;diff[1] += 1;diff[end + 1] -= 1;}}// 计算前缀和，找到最大乘客数量和对应的最小站点编号int maxCount = 0;int resultStation = 1;int current = 0;for(int i = 1; i <= maxStation; i++){current += diff[i];if(current > maxCount){maxCount = current;resultStation = i;}}// 输出结果cout << resultStation << "\n";return 0;
}🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）
🏆本文收录于，华为OD机试真题（Python/JS/C/C++）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
