OpenAI 的 coding 面试里也很常见一类题，表面看很像普通区间枚举，但一旦真的按所有子数组去扫，时间复杂度会直接炸掉。这道题就是典型代表。
题目给你 1...n 这 n 个元素，再给一批冲突对 (a, b)。如果某个连续区间里同时包含 a 和 b，那这个区间就不合法。问题是：一共有多少个非空连续区间是合法的？
单点区间允许，空区间不允许。
这题最容易误入的方向，就是把它当成“枚举所有 [l, r] 再检查是否合法”的题。但只要 n 上到 10^5，O(n²) 基本没有任何机会。
先看例子，为什么这题本质不是暴力判断
假设：
n = 5allergic = [1, 2]poisonous = [3, 5]
也就是冲突对有两组：
(1, 3)(2, 5)
合法区间包括：
[1][1,2][2][2,3][3][2,3,4][3,4][4][3,4,5][4,5][5]
这个例子里最关键的观察不是“哪些区间合法”，而是：
对每个固定的右端点
r，到底最左可以从哪里开始，才能保证[l, r]合法？
一旦这个最左边界知道了，以 r 结尾的合法区间数就能立刻算出来。
这题真正要算的是：每一列的最左合法起点
把每个右端点 r 想成一列。
如果你知道对这个 r 来说，最左合法起点是 left[r]，那么所有合法区间就是：
[left[r], r][left[r] + 1, r]- ...
[r, r]
所以以 r 结尾的合法区间数量就是：
r - left[r] + 1
整题答案就是把所有右端点的这一项加起来。
也就是说，问题已经从“统计所有合法区间”被改写成了：
如何快速求出每个右端点对应的最左合法起点？
这一步一旦想明白，题目就会从区间枚举题变成线性扫描题。
第一步：先记录每个点左边最大的冲突位置
对于每一对冲突 (a, b)，不妨先整理成 a < b。
如果我们把 b 看成右端点，那么只要一个区间包含了 a 和 b，它就非法。这意味着：
当右端点来到 b 时，左边界就绝对不能再放到 a 或更左，否则 a 和 b 会同时被包含进来。
因此，对每个位置 b，我们只需要关心：
在它左边，最大的那个与它冲突的点是谁？
为什么只看最大的那个？
因为它会给左边界带来最强的限制。比它更小的冲突点，不会比它更“靠右”，所以约束更弱。
在上面的例子里，我们会得到：
1左边没有冲突点2左边没有冲突点3左边最大的冲突点是14左边没有新增冲突点5左边最大的冲突点是2
这一步可以用哈希表或数组去维护，每条冲突边只处理一次。
第二步：为什么“当前冲突点 + 1”还不够
很多人走到这里，会觉得答案已经出来了：
如果右端点是 r，那最左合法起点不就是“最大冲突点 + 1”吗？
这个想法只对了一半。
原因在于，右端点往右移动时，前面已经形成的限制不会消失。
还是上面的例子：
- 当
r = 3时，因为(1,3)这条边存在，所以左边界至少要从2开始 - 当
r = 4时，虽然4自己没有新冲突，但[1,4]依然不合法，因为它还是包含了1和3
这说明什么？
说明右端点来到 4 时，左边界限制至少仍然要保持在前一列的水平，不能因为“当前点没有冲突”就退回去。
所以真正的转移关系是：
当前列的限制 = 当前新增限制 和 前一列限制 里的较大者
本质上，这就是一个前缀最大值传播。
正确的核心转移
设 bad[r] 表示：当右端点是 r 时，左边最大的冲突位置。
那么真正有效的限制不是原始的 bad[r]，而是它的前缀最大值。
因为所有更早出现过的冲突约束，都会继续影响后面所有右端点。
于是从左到右扫一遍时：
- 当前位置的限制，要和前一个位置继承下来的限制取最大值
- 一旦这个最大限制确定了，最左合法起点就是
maxBad[r] + 1 - 以
r结尾的合法区间数就是r - maxBad[r]
这里之所以不是 +1，是因为：
- 最左起点是
maxBad[r] + 1 - 可选起点总数是
r - (maxBad[r] + 1) + 1 = r - maxBad[r]
这就是整题 O(n) 统计的来源。
这题为什么能做到线性
整个流程其实很紧凑：
- 扫一遍所有冲突对，把每个右端点的“左侧最大冲突点”记下来
- 再从
1到n做一次前缀最大值传播 - 顺手累加每个右端点贡献的合法区间数
如果冲突对数量记为 m，总复杂度就是：
- 时间复杂度：
O(n + m) - 空间复杂度：
O(n)
这也是这题在 n = 10^5 级别下可以稳定通过的根本原因。
这题最容易错的地方
1. 把它写成区间暴力枚举
这是最直接的超时来源。
只要你还在想“固定左端点，再往右扩”，基本已经偏离正解方向了。因为这题真正该固定的是右端点，而不是尝试验证每个区间本身。
2. 只看当前位置的新冲突，不继承前面的限制
这是最常见的逻辑 bug。
很多同学能想到给每个 b 记录一个最大的 a，但没有意识到旧限制会持续影响之后所有位置，于是答案会在中间某些列突然变大，导致多算。
3. 没有先统一成 a < b
冲突对本身没有方向，但在这道题里我们讨论的是“右端点的左侧最大限制”，所以必须先把每条边标准化成左小右大，才能统一处理。
4. 数贡献时下标关系写错
这类题最后经常不是模型错，而是：
- 左边界是从
maxBad + 1开始 - 区间个数算成了
r - left + 1
一旦下标没扣清楚，很容易多一个或者少一个。
OpenAI 在这题里真正考什么
这题看起来像计数题，但本质上在考的是：
- 你能不能把“区间是否合法”改写成“右端点受什么限制”
- 你能不能识别出限制是单调继承的
- 你能不能把局部冲突压成全局可递推的信息
这正是 OpenAI coding 题里也很常见的风格：
- 题面看似业务化
- 暴力方向很自然，但一定超时
- 真正正解通常来自某个“状态压缩后的单调结构”
只要你抓住这点，这类题就会顺很多。
📌 最后总结
这道题最值得记住的，不是某个模板，而是这个转化过程：
- 原问题：统计所有合法连续区间
- 关键改写：对每个右端点，求最左合法起点
- 核心结构：每个位置记录左侧最大冲突点，再做前缀最大值传播
一旦这样看，整题就从 O(n²) 直接降到 O(n + m)。
如果你最近在准备 OpenAI coding 面试，这类“把区间合法性改写成边界递推”的题型非常值得专门练。很多时候，真正的门槛不是实现，而是你有没有及时看出应该固定哪一端。
🚀 oavoservice：你的 OpenAI Coding 面试稳过保障
面对 OpenAI 这种看似是区间题、实则考建模与复杂度控制的 coding 面试，你需要的不只是一份答案，而是一个专业的技术团队支持。
我们提供：
✅ HackerRank 满分代写 — 高频题库持续覆盖
✅ 代码符合工业级规范 — 逻辑清晰，边界完整
✅ 实时场外助攻 — 无痕辅助，不干扰正常操作
✅ 7x24 小时在线 — 随时待命
不要让一道复杂度看错的 coding 题，影响你冲 OpenAI 的机会。
We consistently provide professional coding interview support services for major tech companies like OpenAI, Google, TikTok, and Amazon. Feel free to contact us if you're interested.
👉 立即添加微信：Coding0201
帮你把 OpenAI coding 这一轮稳住。
Telegram: @OAVOProxy
Gmail: [email protected]