★ FEATURED ARTICLE 最近几个月我身边陆续有人投某大厂的OD岗位机考环节让大家最紧张的不是算法本身而是“双机位”三个字。一台电脑摄像头正对着脸一台手机架在侧后方45度盯住键盘和屏幕全程录音录像系统一旦判定切屏或视线偏离轻则警告重则取消资格。在这种环境里写代码连打开本地IDE的代码提示都要先考虑是否被监控更别提临时搜资料。这种压力下“区间交集”这种C卷里经常出现的题反而成了很多人的分水岭会的人几分钟写出双指针AC不会的人盯着两个区间列表半天不知道从哪里下手。这篇文章就围绕区间交集的Java解法展开把双指针思路、完整代码、边界条件、机考环境下的避坑经验一次讲清楚。适合三类人读正在准备大厂OD机考、想提前适应双机位考试节奏的求职者想快速掌握区间类算法题通用模板的人笔试时总在边界条件上栽跟头、希望系统化补短板的开发者。1. 机考背景与区间交集题解思路1.1 双机位机考到底在考什么OD这类外包开发岗的招聘通常会经过简历筛选、机考、技术面试等环节机考是第一道硬性门槛。整套流程中双机位监考给不少人造成了额外压力。考试前官方会提前发来链接进入系统后先做环境检测电脑摄像头画面是否正常、浏览器有没有权限调用麦克风、屏幕共享是否成功。检查通过后还要用手机扫码加入副机位手机固定在身体侧后方保证能同时拍到键盘和屏幕。这个机位角度一旦不合格系统会预警人工监考也会不定时查看画面。试卷结构一般是基础题加两道编程题基础题包括单选、多选、填空编程题则是从题目池里随机抽取组合。题目池按批次分成A、B、C、D等不同卷号C卷并不是网上传的“地狱难度”它只是一套随机组合卷里面出现的算法题大概率还是双指针、排序、贪心、动态规划这些经典类型。区间类题目因为贴近实际业务里的排班、会议室、日程等场景出题率一直很高区间交集就是很有代表性的一个。建议第一次参加机考的朋友考前一晚就把摄像头、麦克风、手机支架、充电线全部准备好考试中不需要的浏览器标签页全部关掉。这些事看起来和算法无关但一旦系统弹出“检测到切屏”的警示思路断掉再恢复浪费的时间远比想象中多。1.2 区间交集这道题在说什么题目描述通常长这样给定第一个区间列表 firstList 和第二个区间列表 secondList每个列表里的区间都按左端点升序排列并且列表内部没有重叠区间。要求返回两个列表的交集区间结果也需要按左端点升序排列。这里的“区间”指闭区间比如 [0, 2] 表示从时间点0到时间点2两端都包含。我用一个标准样例来走一遍firstList [[0,2],[5,10],[13,23],[24,25]]secondList [[1,5],[8,12],[15,24],[25,26]]手动计算[0,2] 与 [1,5]左端点取大的是1右端点取小的是2交集 [1,2][5,10] 与 [1,5]左端点取大的是5右端点取小的是5交集 [5,5][5,10] 与 [8,12]交集 [8,10][13,23] 与 [15,24]交集 [15,23][24,25] 与 [15,24]左端点取大的是24右端点取小的是24交集 [24,24][24,25] 与 [25,26]交集 [25,25]所以最终结果应该是 [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]。这里有两个很容易被忽略的点。第一[5,5]、[24,24] 这种长度为0的单点区间在闭区间语义下算合法交集不能丢。第二[24,25] 和 [25,26] 这种“端点相接”的情况因为两边都包含25所以 [25,25] 同样要输出。很多新手在自测时漏掉这两种情况导致提交后用例不过。1.3 为什么双指针是标准解而不是暴力枚举看见区间题第一反应可能是暴力两层for循环把 firstList 和 secondList 的区间两两组合逐一判断是否有交集。这种写法简单直接时间复杂度 O(m*n)。当 m、n 都到几百时还能跑规模一旦上到10^5完全不可能通过。题目里有两个隐藏条件每个列表内部区间有序且互不重叠。这两个条件合在一起恰好满足双指针扫描的前提——我们可以像归并两个有序数组一样用两个下标 i、j 从两个列表头部同时出发每次只比较当前两个区间然后移动其中一个指针。为什么移动右端点较小的区间所在指针就一定正确理由是更早结束的区间已经没有机会和对方的后续区间产生交集。如果 A 的右端点小于 B 的右端点那么 B 的下一个区间左端点一定大于 B 的当前右端点因为 B 内部不重叠于是也一定大于 A 的右端点所以 A 当前的区间不可能再与 B 的下一个区间重叠。它的使命已经完成可以安全后移。用生活例子说明A部门订了会议室9点到10点B部门订了9点半到11点当前重叠时段是9点半到10点。处理完这段后A在10点就结束B还占用到11点但B的下一个使用时段最早从11点开始。A接下来最早也只能从10点开始安排所以A的下一个时段最多与B当前时段比较不可能与B的下一个时段重叠。让A的指针后移去和B的当前区间比较不会漏解。所以双指针方案的时间复杂度是 O(mn)空间复杂度在只记结果的情况下是 O(1)不计返回数组。对机考这种限时场景这是最优也最好写的方案。2. Java实现代码模板与边界细节2.1 直接可提交的Java代码先给一版经典实现方法名和参数风格适配大部分机考平台import java.util.ArrayList; import java.util.List; public class Main { public int[][] intervalIntersection(int[][] firstList, int[][] secondList) { int i 0; int j 0; Listint[] result new ArrayList(); while (i firstList.length j secondList.length) { int lo Math.max(firstList[i][0], secondList[j][0]); int hi Math.min(firstList[i][1], secondList[j][1]); // 闭区间判断lo hi 时是单点交集 if (lo hi) { result.add(new int[]{lo, hi}); } // 右端点更小的区间不可能再与对方后续区间相交 if (firstList[i][1] secondList[j][1]) { i; } else if (firstList[i][1] secondList[j][1]) { j; } else { // 两个当前区间都已经处理完指针同时后移最合理 i; j; } } return result.toArray(new int[result.size()][]); } }这段代码的核心就是三件事求重叠区间的左右端点、判断是否有效、移动右端点更小的指针。如果你在本地IDE自测需要补一个 main 方法和 import java.util.Arrays;才能打印数组。机考平台如果是核心代码模式只提交类和方法即可不要把 main 里的自测代码一起交上去否则可能编译不通过。2.2 边界条件逐项过筛自测时一定要覆盖下面几类用例场景输入预期输出说明空列表firstList[], secondList[[1,3]][]while条件不满足直接返回空完全不相交[[1,3]] 和 [[4,5]][]lo4hi3lohi不成立端点相接[[1,4]] 和 [[4,5]][[4,4]]闭区间下[4,4]合法完全包含[[1,10]] 和 [[3,4]][[3,4]]只输出重叠部分完全相等[[1,5]] 和 [[1,5]][[1,5]]两个指针都要移动单点区间[[1,1]] 和 [[1,2]][[1,1]]单点也满足lohi重点解释两个误区。第一个是很多人判断交集时写 lo hi这样会漏掉所有长度为0的交集。机考默认闭区间应该用 lo hi。如果题目明确改成“开区间”再改成 lo hi 不迟。第二个误区是“完全包含”场景大多数人会想当然以为要输出整个大区间或者大区间中没被覆盖的部分实际上交集只取公共覆盖范围也就是小区间本身。右端点相等时的处理也值得单独说。如果把判断写成if (firstList[i][1] secondList[j][1]) { i; } else { j; }当右端点相等时只有 j 移动。这种情况下程序不会死循环因为 j 最终会耗尽i 也会随条件继续消耗但每轮只推进一个指针会白白增加循环次数而且代码意图不清晰。用三段式 if/else 同时处理“小于、大于、等于”三种情况边界行为最明确。2.3 Java写法里的三个易失分点第一结果集用 ArrayList 而不是 LinkedList。ArrayList 底层是数组尾部追加和随机访问都很快LinkedList 每个元素都要维护前后指针内存占用更大遍历和转数组更慢。数据量小的时候差别不明显但机考评测数据动不动上万条养成好习惯没坏处。第二toArray 的参数写法。result.toArray(new int[result.size()][]) 可以正常工作也有很多人写 new int[0][]两种都可以。JDK 6之后官方支持 new int[0][]但我更推荐传 result.size()语义直观也不会触发旧版JVM里额外的反射分配。第三不要在结果已经有序时额外调用 Arrays.sort。双指针扫描天然按左端点升序输出因为两个输入列表都有序交集区间的左端点只会来自扫描顺序靠前的区间不会乱序。额外排序不仅浪费性能还可能把本来正确的顺序弄乱属于画蛇添足。3. 题外题内输入输出与复杂度控制3.1 核心代码模式与完整程序模式某大厂的OD机考大部分时候是核心代码模式系统已经把输入数据解析成方法参数你只需要写方法体。但不同批次、不同平台的习惯不完全一样也有的用ACM模式要求自己从标准输入读取数据并打印结果。两种模式都要心里有数。如果是核心代码模式只需要保证方法签名正确。比如题目要求的方法是 public int[][] intervalIntersection(int[][] firstList, int[][] secondList)你多写一个同名重载方法没关系但主方法的类名必须和平台要求一致通常是 Main 或 Solution写错类名直接编译失败。如果遇到需要自己处理输入输出的版本比如输入格式是4 4 0 2 5 10 13 23 24 25 1 5 8 12 15 24 25 26可以这样读import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); String[] firstLine br.readLine().split( ); int m Integer.parseInt(firstLine[0]); int n Integer.parseInt(firstLine[1]); int[][] firstList new int[m][2]; String[] firstValues br.readLine().split( ); for (int i 0; i m; i) { firstList[i][0] Integer.parseInt(firstValues[i * 2]); firstList[i][1] Integer.parseInt(firstValues[i * 2 1]); } int[][] secondList new int[n][2]; String[] secondValues br.readLine().split( ); for (int j 0; j n; j) { secondList[j][0] Integer.parseInt(secondValues[j * 2]); secondList[j][1] Integer.parseInt(secondValues[j * 2 1]); } int[][] result new Main().intervalIntersection(firstList, secondList); // 按题目要求的格式输出通常是 [[1,2],[5,5]...] 这种字符串 StringBuilder sb new StringBuilder([); for (int[] interval : result) { sb.append([).append(interval[0]).append(,).append(interval[1]).append(],); } if (result.length 0) { sb.deleteCharAt(sb.length() - 1); } sb.append(]); System.out.println(sb); br.close(); } }用 BufferedReader 而不是 Scanner 的原因是机考数据量大时 Scanner 的 nextLine 偶尔会在数据流边界上卡顿BufferedReader 更稳。当然如果是核心代码模式这部分完全用不到。3.2 时间复杂度空间复杂度的一次算清时间上两个指针 i 和 j 只会递增不会回退所以while循环总共执行不超过 mn 次。每次循环做常数次比较和赋值总复杂度 O(mn)。对比暴力法的 O(m*n)当 mn100000 时暴力法需要10^10次操作Java跑完可能超时几十倍双指针只需要2×10^5次操作毫秒级完成。这就是考察有序结构识别能力的意义。空间上除了返回结果集额外只用了两个下标、两个局部端点变量额外空间 O(1)。count这个结果集本身是必须返回的不算额外内存。还有一个容易被追问的点为什么两个输入列表都“有序且互不重叠”是关键如果输入乱序需要先分别按左端点排序然后还要处理排序后可能出现的内部重叠整个题目就会变成“先合并再取交集”复杂度升高。题目的天然有序条件就是暗示你用双指针而不是先排序再暴力。3.3 手工验证用例的完整过程考场上写完后不要只跑一遍样例就提交。我习惯画一张指针追踪表跟着代码走一遍标准样例会步骤ifirstList[i]jsecondList[j]lohi是否加入指针移动10[0,2]0[1,5]12加入[1,2]i21[5,10]0[1,5]55加入[5,5]j31[5,10]1[8,12]810加入[8,10]i42[13,23]1[8,12]1312不加入j52[13,23]2[15,24]1523加入[15,23]i63[24,25]2[15,24]2424加入[24,24]j73[24,25]3[25,26]2525加入[25,25]i结束特别注意第4步[13,23] 和 [8,12] 没有交集但此时哪个指针该动答案是 j因为当前两个区间中secondList的右端点12更小它已经不可能与后面的 [24,25] 相交所以移动 j。很多人在这里写反成 i会直接漏掉后续结果。4. 双机位机考避坑经验实录4.1 环境准备阶段最容易翻车的地方双机位考试对环境的严苛程度比想象中高很多。我整理几个真实出现的翻车点摄像头权限有些浏览器默认禁用摄像头考试前不会自动弹窗。提前进入系统做设备检测确认画面里能看到自己。副机位角度手机放正前方不行侧面20度也可能不合格。最好是侧后方45度左右能拍到键盘、手和屏幕。没有支架就用几本书垫角度要提前试。手机锁屏很多考试App要求手机常亮锁屏会导致第二机位断线。考前把自动锁屏时间调到最长插着充电器保持亮屏再开勿扰。网络环境考试中断网很多平台会直接锁定试卷不会等你恢复。建议用网线直连Wi-Fi备用手机副机位走流量问题不大。切屏判定不要以为只有“切到浏览器其他标签页”才算切屏。有些系统把点击IDE外的区域、按Windows键、AltTab切换窗口都记为切屏。最稳妥的做法是答题前把所有不相关程序关掉尽量在系统在线IDE里直接写。还有一条容易被忽略有些平台在考试中途会要求考生展示周围环境人工监考可能突然发文字消息要求调整机位。这时不要慌按指令操作即可正常调整不会被判违规。4.2 编码过程中的高频踩坑第一个坑是空数组判断。代码里 while (i firstList.length j secondList.length) 已经能安全处理空列表因为长度为0时不进入循环。但如果有人在循环体里写 firstList[i][0] 之前没有判断 i firstList.length就会越界。加了判空会让代码更稳也能让阅卷人一眼看出你考虑过输入为空的情况。第二个坑是结果集的构建方式。有人想“先扫一遍统计交集数量再开一个固定大小数组填充”这样可以避免动态扩容但代码逻辑分两遍出错的概率更高。用 Listint[] 动态添加最后 toArray 转换逻辑最直接。第三个坑是判断条件写成 lo hi 而不是 lo hi。这个问题在前面提过但因为实际踩的人太多再强调一次。闭区间两端都包含左端点等于右端点时依然是有效交集。第四个坑是误以为结果需要去重。两个区间在同一个点上重叠输出 [5,5] 是有意义的不要因为“单点不算一个时间段”就把这类结果去掉。题目没有明确说排除单点就不能自己加约束。4.3 时间分配与检查策略我给自己定的标准是区间交集这类中等偏易的题从读题到AC控制在25分钟以内。具体拆分如下阶段时间做什么读题理解3分钟确认闭区间/开区间、输入输出格式、边界条件思路确认5分钟确认双指针方案与复杂度写代码10分钟编写主体逻辑确认类名与方法签名自测5分钟跑样例再用空数组、单点、全不相交三类用例自测提交2分钟检查代码格式确认没有把自测 main 方法一起提交如果在第3阶段卡住超过15分钟还没跑出预期结果有两个选择先写暴力 O(m*n) 版本拿部分分回头再优化或者直接标记题目先做后面的题。机考判分按通过用例比例给分部分分很有价值。一个小技巧写完主体逻辑后用嘴把代码“讲”一遍。比如“firstList右端点小就让isecondList右端点小就让j相等就都移动”。讲的过程最容易发现指针移动条件写反这类低级错误。5. 三类区间变体一套模板吃透5.1 变体一合并区间合并区间是区间类题目里最常出现的变体。给定若干个可能有重叠的区间要求合并所有重叠部分并输出新的无重叠列表。经典例子[[1,3],[2,6],[8,10],[15,18]]输出 [[1,6],[8,10],[15,18]]。做法是先按左端点升序排序再维护当前合并区间的右端点Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0])); Listint[] merged new ArrayList(); for (int[] interval : intervals) { if (merged.isEmpty() || merged.get(merged.size() - 1)[1] interval[0]) { merged.add(interval); } else { merged.get(merged.size() - 1)[1] Math.max( merged.get(merged.size() - 1)[1], interval[1]); } }这个模板和区间交集刚好是相反方向区间交集合是在两个列表之间找重叠合并区间是在单个列表内部消除重叠。共同点在于都需要比较右端点。注意排序时建议用 Integer.compare(a[0], b[0])而不是 a[0] - b[0]。虽然正常范围下后者也没问题但用比较器调用更稳也能避免整数溢出。机考时如果数据范围特别大减法排序可能踩坑。5.2 变体二插入区间插入区间是合并区间的近亲。题目会给一个已经按左端点升序排列、且内部无重叠的区间列表再给一个新区间要求把新区间插入并合并最后输出新的无重叠列表。经典例子intervals [[1,3],[6,9]]newInterval [2,5]输出 [[1,5],[6,9]]。最简单的写法是把新区间加入列表然后对整个列表调用合并区间模板。这样代码只有十几行但排序带来 O(n log n) 复杂度。如果题目数据量大或者面试官期望 O(n)可以改为一次扫描Listint[] result new ArrayList(); int i 0; int n intervals.length; while (i n intervals[i][1] newInterval[0]) { result.add(intervals[i]); i; } while (i n intervals[i][0] newInterval[1]) { newInterval[0] Math.min(newInterval[0], intervals[i][0]); newInterval[1] Math.max(newInterval[1], intervals[i][1]); i; } result.add(newInterval); while (i n) { result.add(intervals[i]); i; }核心逻辑是先把新区间左侧且不重叠的区间直接放入结果然后不断吞并与新区间重叠的区间动态扩大新区间边界最后把右侧剩余区间放入结果。这段代码和区间交集的思路同源区别在于一个是找重叠一个是消重叠。5.3 变体三最大重叠点数这个变体常见于“会议室问题”给若干开会时间段问同一时刻最多有多少个会议在开。解法叫扫描线把每个区间拆成开始和结束两个事件开始使计数加1结束使计数减1然后按坐标顺序扫描维护计数最大值。用 TreeMap 让坐标自动排序代码非常紧凑TreeMapInteger, Integer map new TreeMap(); for (int[] interval : intervals) { map.put(interval[0], map.getOrDefault(interval[0], 0) 1); map.put(interval[1], map.getOrDefault(interval[1], 0) - 1); } int cur 0; int max 0; for (int count : map.values()) { cur count; max Math.max(max, cur); }举个例子[[0,30],[5,10],[15,20],[18,23]]在时间18到20之间同时有三个区间覆盖扫描线算法能准确算到最大值3。这个变体和区间交集用的思想不同但都在区间端点的时间轴上做文章遇到“重叠数最大”“同时占用”这类关键词时优先考虑扫描线。5.4 机考选题见到这些关键词选对模板区间类题目在机考里出现时关键词会提示你选哪个模板题型关键词模板区间交集两个列表、交集、共同占用、重叠部分双指针合并区间合并、重叠合并、去掉重复区间排序扫描插入区间插入新区间、保持有序、合并一次扫描或复用合并模板最大重叠点数最多同时、峰值、重叠数量最大扫描线(TreeMap或差分数组)把这套对应关系记熟遇到区间题就能很快锁定方向不用再从头分析。6. 结语给正在刷题的你我个人实际备战时把区间交集这道题刷了三遍。第一遍在IDE里看题解默写第二遍合上题解从零手写第三遍故意把边界条件删掉看自己能不能在10分钟内把代码恢复到完整状态。三遍之后这个解法基本变成肌肉记忆后面再遇到合并区间、插入区间也只是在模板上做加减法。最后再分享一个小技巧考前一天不要狂刷新题把双指针区间模板、边界自测四件套空数组、单点区间、完全包含、完全不相交过一遍比临时抱佛脚刷十道新题更稳。机考拼的是稳定输出不是临场爆发。双机位盯得再紧只要手里有可靠的代码模板心里就有底。
阅读完成 · 觉得有帮助？
