LeetCode: Insert Interval & Merge Interval

叁歲伎倆 2022-08-07 14:35 179阅读 0赞

**1、Insert Interval**

Description: Given a set of non-overlapping intervals, the intervals were initially sorted according to their start times, insert a new interval into the intervals (merge if necessary).

Example: Give`[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].`

题意：将一个新的区间插入到一组有序的区间中，并根据需要对区间进行合并。

思路：因为区间是有序的，那么下一个区间的起始值肯定大于上一个区间的结束值，因此可以将区间映射到一个数组中，每个区间的两个值对应数组中的两个相邻的元素，那么构造的数组也一定是有序的。如下所示

![Center][]

构造完数组后，我们可以查找新的区间对应的起始值在数组中位置，并根据位置合并相应的区间。

因此可以构造如下算法：

step 1： 根据区间构造新的数组;

Step 2：在数组中找到第一个比新区间的起始值大的元素），并判断该元素与原区间的关系，分为两种：

1）原区间起始值：例如插入\[11, 13\]，先判断比11大的第一个元素时12，12对应原区间\[12,16\]的起始值，接下来要找一个大于新区间的结束值的元素，即找到16，那么可以发现\[11,13\]与区间\[12,16\]存在覆盖，那么就可以将两者合并为\[11,16\]。如果两个区间有覆盖(如下图)，找到两个区间的最小起始值作为合并后的起始值，两个区间的最大结束值作为合并后区间的结束值。否则，新区间将作为一个单独的区间插入结果集中。

![Center 1][]

2） 原区间结束值：这样就可以判断新区间的起始值在该元素对应的原区间中，所以不管原区间的结束值在哪，都会存在区间覆盖，而且原区间的起始值会成为合并后的区间的起始值，然后判断新区间结束值得位置，来确定合并后区间的结束值。

![Center 2][]

程序代码如下：

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            List<Interval> result = new ArrayList<Interval>();
    		if(intervals.size() == 0) {
    			result.add(newInterval);
    			return result;
    		}
    		int size = intervals.size();
    		int[] ele = new int[2*size];
    		//将区间映射到数组中
    		for(int i=0; i<size; i++) {
    			ele[2*i] = intervals.get(i).start;
    			ele[2*i+1] = intervals.get(i).end;
    		}
    		int newS = newInterval.start; //合并后区间的起始值
    		int newE = newInterval.end;   //合并后区间的结束值
    		int i = 0;
    		for(; i<ele.length && ele[i]<newInterval.start; i++) {
    			if(i % 2 == 1)  
    				result.add(intervals.get(i/2)); //原区间直接加到结果集中 
    		}
    		newS = (i%2==0) ? newInterval.start : ele[i-1];  //有gap时，确定合并后区间起始值
    		if(i == ele.length) {
    			newE = newInterval.end;
    			result.add(new Interval(newS, newE));
    			return result;
    		}
    		while(i<ele.length && ele[i]<=newInterval.end) {
    			i++;
    		}
    		newE = (i%2==0) ? newInterval.end : ele[i];  //存在gap时，确定合并区间的结束值
    		result.add(new Interval(newS, newE));   //将合并后的区间加到结果集
    		while(i < ele.length) {  //将剩余的区间加到结果集中
    			if((i+1) % 2 == 1)
    				result.add(intervals.get(i/2));
    			i++;
    		}
    		return result;
        }

**2、Merge Interval**

Description: Given a collection of intervals, merge all overlapping intervals. Example: Given \[1,3\],\[2,6\],\[8,10\],\[15,18\], return \[1,6\],\[8,10\],\[15,18\].

思路：由于题目没有说明原来的结果集有序，因此在实现的时候应该先对原区间根据起始值进行排序。然后，对于遍历每个区间，判断是否存在gap，如果存在gap，进进行合并，否则直接添加到结果集中。

public List<Interval> merge(List<Interval> intervals) {
            if(intervals.size() == 0)
            	return new ArrayList<Interval>();
            List<Interval> result = new ArrayList<Interval>();
            int size = intervals.size();
            //使用匿名类实现对区间的排序
            Comparator<Interval> comparator = new Comparator<Interval>() {
            	public int compare(Interval I1, Interval I2) {
            		return I1.start - I2.start;
            	}
    	};
    	Collections.sort(intervals, comparator); //对原区间集合排序
            int start = intervals.get(0).start;  //初始化合并区间的起始值
            int end = intervals.get(0).end;     //初始化合并区间的结束值
            for(int i=1; i<size; i++) {  
            	if(end >= intervals.get(i).start) {  //存在gap
            		start = start<intervals.get(i).start ? start : intervals.get(i).start;  //确定合并区间的起始值
            		end = end>intervals.get(i).end ? end : intervals.get(i).end;  //确定合并区间的结束值
            	} else {
            		result.add(new Interval(start, end));  //不存在gap，或者合并区间与后面区间没有gap，添加到结果集
            		start = intervals.get(i).start;  //重新初始化合并区间起始值
            		end = intervals.get(i).end;    //重新初始化合并区间结束值
            	}
            }
            result.add(new Interval(start, end));  //将最后一个区间加入到结果集
            return result;
        }

[Center]: /images/20220805/f0bef9d6491545eb8e89c49b01d4e9be.png
[Center 1]: /images/20220805/5fc9e4e444aa4e7695ae5ed653a84be5.png
[Center 2]: /images/20220805/7bb36eb3a9b94ae9b36b01f1d65eba0e.png