LeetCode - Merge Intervals

LeetCode - Merge Intervals

問題描述： 對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;
}