【LeetCode】57. Insert Interval

问题描述

https://leetcode.com/problems/insert-interval/#/description

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].

将一个interval插入到已经排序好了的intervals中

算法

因为已经排序好了，所以只需要一个个遍历比较看是否需要合并，然后将其添加到结果数组中即可。
遍历时，设当前interval为it，会发生以下三种情况：

1. newInterval在it前面，表现为newInterval.end < it.start，此时先添加newInterval，后添加it，因为newInterval已经添加进去了，所以后面的就无需比较了
2. newInterval在it后面，表现为newInterval.start > it.end，此时只添加it到结果数组中即可，让newInterval再与后面的去比较
3. 两者有重叠部分，需要合并，将it合并到newInterval中

代码

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
	        List<Interval> res = new ArrayList<>();
	        boolean hasInserted = false; // 是否已插入newInterval
	        for(Interval it:intervals) {
	        	if(hasInserted || it.end < newInterval.start) {
	        		res.add(it);
	        	} else if(it.start > newInterval.end) {
	        		res.add(newInterval);
	        		res.add(it);
	        		hasInserted = true;
	        	} else {
	        		newInterval.start = Math.min(newInterval.start, it.start);
	        		newInterval.end = Math.max(newInterval.end, it.end);
	        	}
	        }
	        if(!hasInserted) {
	        	res.add(newInterval);
	        }
	        return res;
	    }

LeetCode解题代码仓库：https://github.com/zgljl2012/leetcode-java