LeetCode -- Insert Interval

LeetCode -- Insert Interval

題目描述：




Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).


You may assume that the intervals were initially sorted according to their start times.


Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].


Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].


This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].




本題要求，對於一個已排序好的間隔序列，插入一個新的間隔，需要保證已排序，並且合並overlap的間隔。




本題的復雜度在於情況數間隔的起始和結束位置的判斷，需要分情況討論。


思路：
1. 首先判斷新間隔i的end是否比intervals[0].start小，如果是：插入在第一個。
2. 判斷i.start是否比intervals.[Count].end 大，如果是：放最後
3. 遍歷Intervals，對於start：
a.gap:start 位於intervals[i].end和intervals[i+1].start之間，startIndex = i
b.between:start 位於intervals[i].start,和intervals[i].end之間, startIndex = i-1;
c.start比intervals[0].start小,startIndex=-1
d.確定startIndex (之後用於確定是否添加到result中)


確定start的情況後，起1個內循環j∈[i,Count)找到end符合的情況：
a.gap: end 位於intervals[i].end和intervals[i+1].start之間 endIndex = j + 1
b.start 位於intervals[i].start,和intervals[i].end之間, endIndex = j+1
c.end比intervals[Count].end大, endIndex = Count+1
d.確定endIndex


4.1 : 將[0,startIndex]間的間隔添加到集合
4.2 : 將combine後的interval，添加到集合。
4.3 : 將[endIndex,Count)間的間隔添加到集合中




實現代碼：

/**
 * 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 Insert(IList intervals, Interval newInterval) {
    // intervals is empty , return new interval    
    if(intervals.Count == 0){
		return new List(){newInterval};
	}
	
	var result = new List();
	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;
	
    }
}

版權聲明：本文為博主原創文章，未經博主允許不得轉載。