区间合并(IntervalMerging)

xiaoxiao2021-03-01  21

    /* 区间合并  给出若干闭合区间,合并所有重叠的部分。      * [                         [         (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),代表区间。

转载请注明原文地址: https://www.6miu.com/read-4149931.html

最新回复(0)