华为OD机试 2024E卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+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。
- 计算前缀和：通过遍历差分数组，累加得到每个站点的实际乘客数量。
- 找出最大乘客数量的站点：遍历前缀和数组，记录乘客数量最多的站点编号，若有多个站点数量相同，则选择编号最小的站点。
六、Java算法源码
public class OdTest {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取员工人数int N = scanner.nextInt();// 初始化数组存储上车和下车站点int[][] intervals = new int[N][2];int maxStation = 0;// 读取每位员工的上车和下车站点，并找到最大站点编号for (int i = 0; i < N; i++) {intervals[i][0] = scanner.nextInt(); // 上车站点intervals[i][1] = scanner.nextInt(); // 下车站点if (intervals[i][0] > maxStation) {maxStation = intervals[i][0];}if (intervals[i][1] > maxStation) {maxStation = intervals[i][1];}}// 初始化差分数组int[] diff = new int[maxStation + 2];// 处理每位员工的乘车区间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;}}// 输出结果System.out.println(resultStation);scanner.close();}
}
七、效果展示
1、输入
4
1 2
2 3
3 4
4 1
2、输出
1
3、说明
🏆下一篇：华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 E卷 200分）
🏆本文收录于，华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
