当前位置：首页 > news >正文

LeetCode -- Insert Interval

news 来源：原创 2024/4/28 16:15:53

题目描述：

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<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;
	
    }
}