问题描述： 对1组区间合并， 例如[2,4]和[3,6]，则合并为[2,6]
实现思路：
1.对区间的最小值进行排序(O(N* Log N))
2.遍历，分情况进行合并，去重，添加到结果集(O(N?))
对于两个区间的关系，一共分4种情况，注释里面已经注明。
实现代码：
public IList
Merge(IList
intervals) { if(intervals == null || intervals.Count == 0){ return new List
(); } var result = new List
(); intervals = intervals.OrderBy(s=>s.start).ToList(); var len = intervals.Count; for(var i = 0;i < len; i++){ // - add or merge into result bool merged = false; foreach(var r in result){ // |-------| : r // |---| : intervals[i] if(r.end < intervals[i].start){ // no interset continue; } // |-------| : r // |---| : intervals[i] else if(r.end == intervals[i].start){ r.end = intervals[i].end; merged = true; break; } // |------------------| : r // |-----| : intervals[i] else if(r.end >= intervals[i].end){ // do nothing merged = true; break; } // |--------| : r // |--------| : intervals[i] else if(r.end < intervals[i].end){ r.end = intervals[i].end; merged = true; break; } } if(!merged){ result.Add(intervals[i]); } } return result; }
?
|