最近刷题圈子里问得最多的就是华为OD机考C卷的“区间交集”这道题几乎成了必刷题。考试是双机位监控屏幕内容全程录像Java代码只能靠硬实力一次写对那种高压环境下很多人连读题都会看错。我模拟考遇到过好几种区间题变体也踩过不少坑这篇就把“区间交集”从题面拆解、核心公式、Java完整实现到考场注意事项全部讲清楚正在准备OD机考或者想补区间算法基础的朋友可以照着这份思路过一遍。1. 先吃透考题双机位C卷的“区间交集”到底在考什么1.1 从考题场景说起C卷区间类题目的出现逻辑先说考试背景。华为OD机考是软件类岗位入职笔试的重要环节机考卷通常分A/B/C卷C卷偏新题和综合题题目难度整体中等但陷阱多、边界多非常考验基础功。双机位是整个考试流程里最让人紧张的部分正面摄像头要拍到人脸和眼睛侧后方机位要拍到你的双手、手机和整个操作桌面考试过程屏幕会录制不允许切屏查资料。也就是说你平时习惯了“先打开搜索引擎搜一下再写代码”的做题方式到了双机位环境下完全行不通必须当场读题、当场建模、当场写完整代码。在这样的规则下出题方反倒更愿意出“看着简单、实际坑多”的题目区间类就是典型代表。区间在业务里非常常见比如时间段重叠判断、IP段合并、优惠券有效期叠加、工单处理窗口期都可以抽象成一堆[start, end]。而C卷的区间交集题正是把“读入区间、求公共交集、处理不存在完整交集的情况”这几个点揉在一起顺便考察你对排序、贪心和边界条件的掌握程度。它不是那种让你五分钟秒杀的送分题也不是那种需要复杂数据结构的难题恰好卡在“大部分人会写但只有一部分人能写对”的位置上。1.2 一道有代表性的题目原型与输入输出约定官方不同批次的题面可能稍微不一样但核心意思大致可以还原成下面这个版本。输入一个整数N表示区间的数量。接下来N行每行两个整数start和end表示一个闭区间[start, end]。请计算所有区间的交集。如果交集存在输出交集区间的左端点和右端点如果交集不存在输出0。以这个题面为例看一下输入输出约定输入 3 1 6 2 8 3 5 输出 3 5三个区间 [1,6]、[2,8]、[3,5] 的交集是 [3,5]因为左端点最大的是3右端点最小的是53小于等于5交集存在。再看一个不存在的例子输入 2 1 2 4 5 输出 0[1,2] 和 [4,5] 没有任何重叠部分公共交集为空输出0。声明一下由于不同批次的题面可能有调整有的版本会要求“不存在时输出false”有的版本会要求输出[-1,-1]甚至有的版本把区间改成开区间这些细节以你实际遇到的考题为准。我这里按最主流的“闭区间不存在输出0”来展开。考试时第一件事是读清楚输出约定这一步做错后面全白搭。1.3 双机位环境下读题的几个易错视角双机位考试最大的敌人不是题目难而是紧张状态下读题漏条件。我见过一个考生把“交集”看成了“并集”代码写得很漂亮结果样例都过不了。区间交集题常见的坑有三个第一区间到底是闭区间还是开区间闭区间包含端点两个区间一个终点是3、另一个起点是3闭区间算有交集开区间算没有第二输出顺序有没有要求有的题要求按左端点升序输出有的只要求输出一对端点第三交集不存在时到底输出什么字符这个每套C卷都可能不同。我的建议是机考开始后先花两分钟把题面完完整整读两遍特别是题目最后一段的“输出说明”和“样例解释”。双机位下你不可能回看视频找答案唯一的权威信息就是题面本身。2. 核心公式与思路拆解为什么一个公式就能搞定全局交集2.1 区间交集就是“最晚的start”和“最早的end”求多个区间的交集很多人第一反应是两两比较先把第一个和第二个求交集得到一个新区间再拿这个新区间去和第三个求交集。这么做理论上没错因为区间交集满足交换律和结合律但写起来要维护中间结果还要处理“中间结果为空”的情况代码容易越写越凌乱。其实多个闭区间的公共交集有一个极简单的数学表达L max(所有区间的start) R min(所有区间的end) 如果 L R交集就是 [L, R]否则交集为空。道理很直白。你可以想象一群人约会议室每个区间代表一个人“最早能到的时间”和“最晚必须走的时间”。所有人能坐在一起开会的时间段开始时间取决于到得最晚的那个人结束时间取决于走得最早的那个人。如果最晚到的人到来之前最早走的人已经走了这场会就开不成也就是交集为空。从数学上也很容易验证。两个区间 [s1, e1] 和 [s2, e2] 的交集是 [max(s1, s2), min(e1, e2)]当 max 小于等于 min 时才有意义。三个区间就是先求前两个的交集再和第三个求交集根据归纳法可以推广到N个区间结果正是全局最大左端点和全局最小右端点。2.2 为什么常见参考答案都会先按start排序你可能注意到一个现象网上搜这道题很多参考答案一上来就是Arrays.sort(intervals, (a,b)-...)排序之后才处理。这里有个容易让人困惑的点求全局交集本身不依赖区间顺序不排序直接遍历也能得到正确答案。那排序是多余的吗不是。把排序换成“默认动作”去理解就顺了。区间类的题目家族里合并区间需要按起点排序因为只有有序才能线性合并最多重叠区间需要按起点排序配合优先队列扫描求两两区间交集也需要排序然后用双指针移动。哪怕当前这道题用不着排序你写上排序也不影响正确性而且向阅卷人传递了一个信号你对区间题型的通用套路是熟知的。更重要的是如果考场上题目变体是“求所有两两区间的交集并输出排序后的结果”没有排序一定会乱套。所以我的建议是拿到区间题先问自己一句“题目输出结果跟顺序有关吗后续操作需要有序性吗”需要就排序不需要就大胆用O(n)公式。这道“区间交集”最简洁的解法不需要排序但你要能解释清楚为什么不需要而不是稀里糊涂地多写一层排序。2.3 复杂度判断O(n)和O(n log n)怎么选机考的时间限制通常很紧张但区间交集这道题N再大也不用怕。不排序的公式法是O(n)时间、O(1)额外空间遍历一次数组就出结果。如果你选择先排序再处理复杂度变成O(n log n)在N10^5级别时排序大约几十毫秒也不会超时。关键不是纠结O(n)还是O(n log n)而是别把复杂度写成O(n^2)。我见过有人对每个区间都和其他所有区间做一次交集判断写完自我感觉良好数据一大直接超时。区间类题目只要N超过一万O(n^2)基本都是死路。机考环境没有调试器等高级工具复杂度分析必须在写代码之前完成。至于数据类型题目说坐标在int范围内但算交集长度或者中间做差值运算时最好直接用long避免面试官后面追加一句“如果坐标扩大到10^9怎么改”。用long初始化端点既不影响AC又让代码更稳。3. Java全实现从读入到交集的完整代码3.1 读入策略数据量一大Scanner真的会拖后腿很多人在本地用IDEA写题习惯用Scanner因为省事。但机考的输入规模一旦到10^5行Scanner的nextInt逐行解析可能会比BufferedReader慢不少极端情况下会产生超时风险。我自己的习惯是直接用BufferedReader加StringTokenizer的组合。import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine().trim()); long[] starts new long[n]; long[] ends new long[n]; StringTokenizer st; for (int i 0; i n; i) { st new StringTokenizer(br.readLine()); starts[i] Long.parseLong(st.nextToken()); ends[i] Long.parseLong(st.nextToken()); } // 到这里n个区间已经全部读入 } }这里把starts和ends拆成两个数组存好处是后续求max和min非常直接。如果你更习惯用二维数组int[][] intervals那就在读入的同时把区间存好。两种方式都能AC但如果后续要做排序或者扫描线二维数组的结构更顺手单纯求交集拆成两个数组更省内存。3.2 最简公式版不到20行解决主体逻辑直接给一个完整的可提交版本类名用Main不加packageJDK 8及以上都能跑。import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine().trim()); long L Long.MIN_VALUE; long R Long.MAX_VALUE; StringTokenizer st; for (int i 0; i n; i) { st new StringTokenizer(br.readLine()); long start Long.parseLong(st.nextToken()); long end Long.parseLong(st.nextToken()); L Math.max(L, start); R Math.min(R, end); } if (L R) { System.out.println(L R); } else { System.out.println(0); } } }注意几个细节。初始化L用Long.MIN_VALUER用Long.MAX_VALUE不能反过来不能都用0。假设所有区间的start都是负的L初始化为0就会导致结果错误。第一轮循环结束后L和R就会变成第一个区间的端点这是符合预期的。判断条件是L R因为题目明确是闭区间端点相等也算有交集。最后输出用System.out.println()默认自带换行。3.3 变体应对最多重叠层数与合并区间的双改写机考最大的变量是“同题型不同问法”。同样是区间题C卷还可能问你“最多有多少个区间重叠”或者“把重叠区间合并后输出”。我建议你备考的时候用一道区间交集顺带把另外两个变体也写了反正核心代码就那么几行。先看最多重叠层数的扫描线写法。思路是按start升序遍历区间用小顶堆维护当前重叠区间的所有end每处理一个新区间先把堆中所有小于当前start的end弹出这些区间已经结束了再把当前区间的end入堆堆的size就是覆盖当前起点的区间数量。import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine().trim()); int[][] intervals new int[n][2]; StringTokenizer st; for (int i 0; i n; i) { st new StringTokenizer(br.readLine()); intervals[i][0] Integer.parseInt(st.nextToken()); intervals[i][1] Integer.parseInt(st.nextToken()); } Arrays.sort(intervals, (a, b) - a[0] ! b[0] ? a[0] - b[0] : a[1] - b[1]); PriorityQueueInteger pq new PriorityQueue(); int maxCnt 0; for (int[] it : intervals) { while (!pq.isEmpty() pq.peek() it[0]) { pq.poll(); } pq.offer(it[1]); maxCnt Math.max(maxCnt, pq.size()); } System.out.println(maxCnt); } }这段代码理解起来并不难堆顶永远是当前堆中所有end的最小值如果堆顶都小于当前start说明堆中已经没有区间能和当前区间重叠全部弹出。剩下的堆内区间start都小于等于当前startend都大于等于当前start所以它们确实都和当前区间有交集。maxCnt就是重叠数最大值。如果想同时输出重叠最多的具体区间段需要在maxCnt更新时把当前的it[0]和pq.peek()存到两个临时变量里等循环结束后输出。合并区间更简单排序后维护当前覆盖区间curStart和curEnd遇到下一个区间时如果它的start小于等于curEnd就扩展右边界否则结束当前段并开始新段。这三类题的底层能力完全一致排序、维护端点、处理边界。你把这套组合拳练顺了无论C卷出哪个变体都不慌。4. 面试官藏在题目背后的三个考点4.1 从公式到贪心你能解释“为什么不需要排序”吗机考的面试环节偶尔会追问“你这个解法为什么对”。很多人的回答是“这样写能过样例”这就把分丢了。对“区间交集”这道题你需要能讲出这样一句话公共交集的左边界不取决于某个特定区间而取决于所有区间中最晚的那个起点右边界取决于所有区间中最早的那个终点。维护这两个极值本身就是贪心思想每一步都取当前最优全局最优由局部极值自然推出。这样解释面试官会认为你确实理解算法本质而不是背模板。同一个逻辑还可以迁移到数组求最大值、字符串公共前缀等题目上公共前缀就是不断取min公共交集就是同时取max和min。把这些概念串起来你的算法知识才是成体系的。4.2 边界测试矩阵手把手把6组数据跑明白考试之前你自己应该先在本地把这些用例全部跑一遍。下面这个表格是我整理的最小测试集覆盖了区间交集的核心边界。测试场景输入预期输出说明单区间1 \n 1 51 5只有一个区间交集就是它本身完全包含2 \n 1 10 \n 2 32 3大区间被小区间“套住”取最晚起点和最早终点端点相切2 \n 1 3 \n 3 53 3闭区间包含端点所以有交集且交集是单点完全不相交2 \n 1 2 \n 4 50L4R2LR交集为空负数坐标2 \n -3 -1 \n -2 1-2 -1初始化不能用0否则直接错大数据量100000行正常输出用O(n)遍历不能用Scanner裸读这6组数据覆盖了“正常、嵌套、相切、空集、负数、大输入”六个维度。机考现场想自己生成测试数据不太现实但至少把前五组手动输入验证一下能挡住绝大多数低级错误。4.3 双机位机考的提交环境准备与15分钟检查清单双机位监考下的提交环境和平时本地IDE完全不一样。首先类名必须是Main不能带package声明不能有public类以外的额外顶层类JDK版本一般支持到Java 8或11lambda表达式和ArrayList都没问题。其次提交时用网页上的在线编辑器代码里不要写中文注释有些平台对中文注释的编码处理不稳定注释全部用英文或者不写。第三不要输出任何提示语比如“请输入区间的个数”这种在本地很常见的引导性输出在线判题会把它们当成答案的一部分直接判WA。考试开始前我一般给自己定一个15分钟环境检查清单第一确认正面摄像头能拍到整个面部和屏幕下缘第二确认侧方机位的支架稳定画面里能看到双手和手机摆放位置第三网页端输入框测试写一个Hello World跑通后再提交一次确保IDE和判题流程正常第四把浏览器通知全部关掉防止考试中被弹窗打断心态。做完这四步再开始看题后面就能专注在算法本身。5. 常见问题与排查技巧实录5.1 典型错误一初始化值用成0负数区间直接错这是我模拟考时第一次踩的坑。当时写的代码是这样的int L 0; int R Integer.MAX_VALUE;输入区间全是负数时比如[-5,-3]和[-4,-1]正确交集是[-4,-3]但我的L一直是0最终输出0。原因就是L没有初始化为逻辑上的“负无穷大”。正确做法要么用Long.MIN_VALUE配合long类型要么读第一个区间后把L和R赋成第一个区间端点再从第二个开始遍历。我建议直接用Long.MIN_VALUE和Long.MAX_VALUE后面就算题目出到负数边界也稳如磐石。5.2 典型错误二空交集时输出格式不对这道题的输出非常死板。题目说空集输出0你输出no intersection肯定WA题目说空集输出false你输出0也WA。另外输出交集的端点时很多考生会顺手输出成[3, 5]带中括号和逗号或者多加一个空格。机考判题是逐字节比对多一个空格、多一个换行都可能判错。我的建议是写一个输出工具小函数专门负责格式化结果比如if (L R) write(L, R); else write(0);所有提交逻辑统一走这个函数。这样即使题目要求变了你也只需要改一个地方。5.3 典型错误三大数据读入和输出拖慢全场Scanner在数据量小于1000时确实很省心但C卷的数据量经常给到10^5以上这时候Scanner会比BufferedReader慢不少。输出也一样每行System.out.println()都要触发一次IO输出量大时耗时明显。我处理大数据量输出的习惯是先用StringBuilder攒着到最后统一flush。不过这道题的输出最多就一行StringBuilder在这里意义不大但读入那一层BufferedReader一定要坚持用。5.4 用“随机区间对拍器”自测在线判题前先给自己判个卷机考提交前你很难知道代码是否覆盖了所有边界所以平时刷题我强烈建议写一个对拍器。思路很简单写一个朴素但绝对正确的算法再写一个你优化的算法然后用随机生成的输入同时跑两个算法对比输出是否一致。这里给一个对拍器的参考思路// 朴素算法从第一个区间开始逐个与当前交集区间求交集 long curL starts[0]; long curR ends[0]; for (int i 1; i n; i) { curL Math.max(curL, starts[i]); curR Math.min(curR, ends[i]); } // 如果 curL curR 输出 curL curR否则输出 0注意朴素算法和优化算法在“求最大交集”这个目标上表述不同但本质一样这里只是帮助你验证边界。真正对拍时你可以用完全不同的实现比如第一版用List两两合并第二版用公式法两个输出只要不一致就说明你的公式法在某个用例上出了问题。随机生成N次每种边界都覆盖之后你提交代码的信心会大很多。6. 个人备考心得与最后建议6.1 把区间题当成一个“模板家族”来刷区间交集不是独立的一道题它和合并区间、最多重叠区间、会议室安排这些题目共享一套底层能力排序、维护端点、扫描线、处理开闭区间。我备考时把这几题放在一起连着刷每天重新默写一遍核心模板连续一周后基本形成肌肉记忆。机考现场看到区间题第一反应不是“这题我不会”而是“这题属于区间家族的哪一类”然后按家族模板快速套用。6.2 双机位考试的心理门槛先求稳再求快双机位监考最难受的是全程被盯着写代码时总觉得有人在看心态容易崩。我的经验是开局先把BufferedReader读入模板敲出来再敲一个空的Main类跑通一次编译这时候心里就有底了。C卷通常两到三题时间分配我会按“简单题30分钟、难题60分钟、剩余时间检查”来切。如果某道题卡了20分钟还想不出正解马上转暴力法或者部分用例解法机考按用例给分拿到部分分永远是优先级更高的选择。6.3 最后分享一个小技巧我每次刷区间题都会把区间交集的公式写在代码注释最前面当作思维锚点交集 [max(start), min(end)]若maxmin则空集。这个公式看似简单但当你紧张到脑子里一团浆糊的时候它就是把你拉回正轨的那根绳子。刷题多了你会发现真正拉开差距的往往不是你能不能写出这个公式而是你在双机位、屏幕录像、心跳加速的情况下还能不能冷静写出这个公式。把模板练到不用想就能敲出来机考就成功了一半。最后再唠叨一句机考的题目描述细节一定会变但区间交集这类基础算法的核心永远是那几个极值、那几条边界。你能把这道题背后的原因讲清楚再把变体代码写熟C卷这道题的分数就到手了。