插入区间：左边留下，中间合并，右边接上
原区间已经有序、互不重叠。新区间左边那些右端还够不着它，原样抄；中间凡是左端还没越过新右端的，并成一段；其余整段接在后面。
线性扫已排序的 intervals。第一段：右端 < 新左端，直接写入。第二段：左端 ≤ 新右端，用 min/max 并进新区间。写入这段合并结果。第三段：剩下的全部写入。时间 O(n)，不必再排序。
给你一组互不重叠、已按左端排序的区间，再给一个新区间。把它插进去，必要时与重叠的原区间合并，结果仍保持有序且不重叠。
主例 intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]，newInterval = [4,8]。[1,2] 完全在 4 左边；[3,5]、[6,7]、[8,10] 都和 [4,8] 相交，并成 [3,10]；[12,16] 完全在 10 右边。答案 [[1,2],[3,10],[12,16]]。
先插入再当 LC56 做也能对，但输入已经有序，再排序是浪费。本文要回答：三段的分界用哪两个不等式切开。
有序输入把列表切成左、中、右
原区间互不重叠且左端有序，所以它们在数轴上从左到右排成一排。新区间 [a,b] 扔进去，原区间只可能落在三类：整段在 [a,b] 左边、和 [a,b] 有交集、整段在 [a,b] 右边。三类在数组里是连续的三段，不会交错。
整段在左：原右端 < a，连端点都碰不到新区间，原样保留。整段在右：原左端 > b，同样碰不到。其余都是重叠，包括相切。缺的不是分类，而是一次从左扫到右、按这个顺序处理，不要把中间段拆开排序。
用手走主例的第一段。[1,2] 的右端 2 < 4，属于左边，写入结果。演示第一帧。下一个 [3,5] 的右端 5 不小于 4，左边段结束。
不必再排序LC56 的排序是因为输入乱序。这里输入已经有序，三段天然连续，线性扫一遍即可。
中间段用 min 左、max 右收成一段
进入重叠段时，用 [a,b] 当当前合并段。只要下一个原区间的左端 ≤ b，它就还粘着当前段：a 改成 min(a, 它的左端)，b 改成 max(b, 它的右端)。左端可能比 a 更小——主例 [3,5] 把左端从 4 拉到 3；右端可能比 b 更大——[8,10] 把右端从 8 推到 10。直到某个区间左端 > b，重叠段结束。
用手走主例。[3,5]：3≤8，并成 [3,8]。[6,7]：6≤8，右端 7 不比 8 大，仍是 [3,8]。演示第一帧。 [8,10]：8≤8，右端扩到 10，变成 [3,10]。演示第二帧。 [12,16]：12>10，重叠结束，写入 [3,10]，再把 [12,16] 整段接上。结果 [[1,2],[3,10],[12,16]]。
新区间也可能和谁都不重叠：左边段结束之后立刻左端 > b，中间循环零次，[a,b] 原样插入。也可能插在最前或最后，第一段或第三段为空。相切要并：原左端等于 b，或原右端等于 a，都算重叠；第一段的判断是右端 < a，不是 ≤。
Go：三阶段
func insert(intervals [][]int, ni []int) [][]int {res := [][]int{}a, b := ni[0], ni[1]i := 0for i < len(intervals) && intervals[i][1] < a {res = append(res, intervals[i]); i++}for i < len(intervals) && intervals[i][0] <= b {a = min(a, intervals[i][0])b = max(b, intervals[i][1])i++}res = append(res, []int{a, b})for i < len(intervals) { res = append(res, intervals[i]); i++ }return res}
1右端 < a 的整段在左，原样写入。主例只写下 [1,2]。
2左端 ≤ b 的都还粘着，同时拉左端、推右端。
3合并结果只插入一次。主例写入 [3,10]。
4下标 i 之后全是右边，整段追加。
总结
左段原样、中段 min/max 并成一条、右段接上。主例插入 [4,8] 后得到 [1,2]、[3,10]、[12,16]。
- 左段分界是原右端 < 新左端。相切不算左边。
- 中段分界是原左端 ≤ 新右端。左端、右端都可能被拉开。
- 输入已有序，不要再当 LC56 排序。