LeetCode 056 Merge Intervals

LeetCode 056 Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

题目大意：

给定几个区间，要求合并重叠区间，返回结果.

解题思路：

A公司的考题。这条题难点在于判断是否合并，怎么合并，新区间合并多个区间。

1. 按start排序。
2. 定义API：如何合并两个区间（两情况），两个区间是否可以合并
3. 遍历每个区间，产生新区间并将其带入到下一轮循环。这是难点，公式为 新区间=新区间+输入区间[i]，这也分为两种情况，可合并和不可合并
   不可合并时，前状态的新区间成为结果，公式为新区间=输入区间[i]。
4. 若不想特别处理循环边界，可加入空区间到末尾（见Java实现，它把新区间=输入区间[i]放入了下一轮）。若不如此做，可将空区间放入开头。

注意事项：

1. 先按左节点排序
2. 区间的右端与另一个区间的左端一样，也算重叠，如[1,2],[2,3]。
3. 原输入加入首节点的左边界fake区间。避免for循环的特殊处理。2. 最后一个区间的情况。
4. 合并后生成新区间，要与下一个继续尝试合并。

Python代码：

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
	intervals.sort(key=lambda x: x[0])
	new_interval = [intervals[0][0], intervals[0][0]]
	res = []
	for interval in intervals:
		if self.can_merge(new_interval, interval):
			new_interval = self.merge_two_intervals(new_interval, interval)
		else:
			res.append(new_interval)
			new_interval = interval
	res.append(new_interval)
	return res

def can_merge(self, interval, interval2):
	return interval[1] >= interval2[0]

def merge_two_intervals(self, interval, interval2):
	return [interval[0], max(interval[1], interval2[1])]

Java代码：

public List<Interval> merge(List<Interval> intervals) {
	Collections.sort(intervals, new Comparator<Interval>(){
		public int compare(Interval v1, Interval v2){
			return v1.start - v2.start;
		}
	});
	intervals.add(new Interval(Integer.MAX_VALUE, Integer.MAX_VALUE));
	List<Interval> re = new ArrayList<Interval>();
	Interval newInterval = null;
	for(int i=1;i<intervals.size();i++){
		if(newInterval==null)
			newInterval = intervals.get(i-1);
		if(canMerge(newInterval,intervals.get(i))){
			newInterval = mergeIntervals(newInterval,intervals.get(i));
		}
		else{
			re.add(newInterval);
			newInterval = null;
		}
	}
	return re;
}


//假设in与in2按start排序，所以只有两情况：
/*
 * In  -------
 * In2   ---
 * In2   -------- 
 */
public boolean canMerge(Interval in, Interval in2){
	if(in2.start == Integer.MAX_VALUE)
		return false;
	return in.end>=in2.start;
}

public Interval mergeIntervals(Interval in, Interval in2){
	return new Interval(in.start, Math.max(in.end, in2.end));
}

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(1)。