LeetCode -- Insert Interval

/**
 * Definition for an interval.
 * public class Interval {
 *     public int start;
 *     public int end;
 *     public Interval() { start = 0; end = 0; }
 *     public Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public IList<Interval> Insert(IList<Interval> intervals, Interval newInterval) {
    // intervals is empty , return new interval    
    if(intervals.Count == 0){
		return new List<Interval>(){newInterval};
	}
	
	var result = new List<Interval>();
	if(newInterval.end < intervals[0].start){
		result.Add(newInterval);
		result.AddRange(intervals);
		return result;
	}
	
	if(newInterval.start > intervals[intervals.Count-1].end){
		result.AddRange(intervals);
		result.Add(newInterval);
		return result;
	}
	
	
	var newAsStart = false;
	if(newInterval.start < intervals[0].start){
		newAsStart = true;
	}
	
	for(var i = 0;i < intervals.Count; i++){
		var startInBetween = newInterval.start >= intervals[i].start && newInterval.start <= intervals[i].end;
		var startInGap = i < intervals.Count - 1 && newInterval.start > intervals[i].end && newInterval.start < intervals[i+1].start;
		
		//try find start fall into which interval or into which gap
		if(newAsStart || startInBetween || startInGap){
			var j = i ;
			// try find end
			var endIndex = -1;
			var endInBetween = false;
			var endInGap = false;
			var endAtLast = newInterval.end > intervals[intervals.Count-1].end;
			if(!endAtLast){
				while(j < intervals.Count){
					if(newInterval.end >= intervals[j].start && newInterval.end <= intervals[j].end){
						endInBetween = true;
						endIndex = j;
						break;
					}
					else if(j < intervals.Count - 1 && newInterval.end > intervals[j].end && newInterval.end < intervals[j+1].start){
						endInGap = true;
						endIndex = j;
						break;
					}
					j++;
				}
			}
			
			Interval combined = null;
			int start = -1;
			int startIndex = -1;
			if(newAsStart){
				startIndex = -1;
				start = newInterval.start ;
			}
			else if(startInBetween){
				startIndex = i - 1;
				start = intervals[i].start;
			}
			else if(startInGap){
				startIndex = i;
				start = newInterval.start;
			}
			
			int end = -1;
			int endAt = -1;
			//found end
			if(endIndex != -1){
				if(endInBetween){
					end = intervals[endIndex].end;
					endAt = endIndex + 1;
				}
				else if(endInGap){
					end = newInterval.end;
					endAt = endIndex + 1;
				}
				
			}
			else if(endAtLast)
			{
				end = newInterval.end;
				endAt = intervals.Count+1;
			}
			// not found end , means new interval end is bigger than the last end 
			else{
				combined = new Interval(start, newInterval.end);
				endAt = intervals.Count+1;
			}
		
			combined = new Interval(start,end);
			
			for(var x = 0;x <= startIndex; x++){
				result.Add(intervals[x]);
			}
			
			result.Add(combined);
			
			for(var x = endAt;x < intervals.Count; x++){
				result.Add(intervals[(int)x]);
			}
			return result;
		}
	}
	
	//new interval start is bigger than all intervals end, just put at end
	
	result.Add(newInterval);
	return result;
	
    }
}

LeetCode -- Insert Interval

原文：http://blog.csdn.net/lan_liang/article/details/48731239