区间合并（IntervalMerging）

    /* 区间合并  给出若干闭合区间，合并所有重叠的部分。      * [                         [         (1, 3),                 (1, 6),         (2, 6),      =>      (8, 10),         (8, 10),              (15, 18)         (15, 18)             ]         ]      */

首先区间是无序的，为了方便我们可以按照区间的左端点大小将区间排序，这样会省很多麻烦，

算法如下（c#）：

private List<Vector2> IntervalMerging(List<Vector2> list) { if (list == null || list.Count == 1) return list; list.Sort((x, y) => (int)(x.x - y.x)); for (int i = 0; i < list.Count - 1;) //循环变量自增运算在循环体内运算 { if (list[i].y < list[i + 1].x) { i++; } else { list[i] = new Vector2(list[i].x, Mathf.Max(list[i].y, list[i + 1].y)); list.RemoveAt(i + 1); //合并后将重合区间删除， //删除后list后面数据自动前移，循环变量不用自增 } } return list; }

我本身是unity开发的，这个是写在unity编辑器下的为了方便就用二维向量（Vector2），代表区间。