Algorithms study cheatsheets
Coding interview 的 Interval cheatsheet
Interval 学习指南，包含练习题、技巧、时间复杂度与推荐资源
Introduction
Interval 问题是 array 的一个子集：给你一个由二元数组组成的数组，每个二元数组代表一个区间的 start 和 end。Interval 属于 array 家族，但有一套常见技巧，因此单独列出。
例子：[[1, 2], [4, 7]]。
Interval 题对新手来说往往比较棘手，因为 overlap 的情况很多。
面试时需要注意
- 先确认
[1, 2]与[2, 3]是否算重叠，这会影响 equality/overlap 判断逻辑。 - 确认
[a, b]是否严格满足a < b。
Corner cases
- 没有 interval
- 单个 interval
- 两个 interval
- 不重叠的 intervals
- 一个 interval 完全被另一个覆盖
- 重复 interval（start/end 完全相同）
- “首尾相接”的区间，例如
[[1, 2], [2, 3]]
Techniques
按 start 排序
最常见的套路：按 interval 的 start 排序。这一步是解 Merge Intervals 的关键。
判断是否重叠
def is_overlap(a, b):
return a[0] < b[1] and b[0] < a[1]
合并两个 interval
def merge_overlapping_intervals(a, b):
return [min(a[0], b[0]), max(a[1], b[1])]
Essential questions
该 topic 必练题。
Recommended practice questions
在掌握基础后推荐练习。