LeetCode - Merge Intervals
问题描述： 对1组区间合并， 例如[2,4]和[3,6]，则合并为[2,6]
实现思路：
1.对区间的最小值进行排序(O(N* Log N))
2.遍历，分情况进行合并，去重，添加到结果集(O(N²))
对于两个区间的关系，一共分4种情况，注释里面已经注明。
实现代码：
public IList<Interval> Merge(IList<Interval> intervals)
{
if(intervals == null || intervals.Count == 0){
return new List<Interval>();
}
var result = new List<Interval>();
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;
}