Problem – Merge Overlapping CI Intervals
Atlassian runs many CI pipelines, and we want to generate reports on usage to find cost-optimization patterns.
Each CI pipeline starts at time X and ends at time Y. We are given a list of pipeline time windows:
[[X₁, Y₁], [X₂, Y₂], ...]
Objective
Find the list of non-overlapping time intervals that cover all times when at least one CI pipeline is running.
In other words, merge all overlapping intervals and return the minimal set of disjoint intervals.
Example
Input:[[2, 5], [12, 15], [4, 8]]
Output:[[2, 8], [12, 15]]
Explanation:
[2, 5]and[4, 8]overlap and merge into[2, 8].[12, 15]does not overlap with them, so it stays as is.- The minimal windows where at least one job is running are
[2, 8]and[12, 15].
思路总结（Brief Idea）
- 先按区间起点
start升序排序。 - 用一个变量
current = [s, e]记录正在合并的区间。 - 依次扫描后面的区间
[ns, ne]：- 若
ns <= e，说明有重叠，更新e = max(e, ne)。 - 否则，把
current放入结果，重新以[ns, ne]作为新的current。
- 若
- 扫描结束后把最后一个
current加入结果。 - 时间复杂度：排序 O(n log n)，扫描 O(n)。
VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 Meta、Google、Amazon 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Stripe 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。
正文完
