【LeetCode】56. Merge Intervals

问题描述

https://leetcode.com/problems/merge-intervals/#/description

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

数轴覆盖问题。

算法

将各条线段的start按从小到大排序，然后依次比较每条线段的end，看是否被前一段覆盖即可。

代码

public List<Interval> merge(List<Interval> intervals) {
	    	List<Interval> res = new ArrayList<>();
	    	if(intervals == null || intervals.isEmpty()) return res;
	    	Collections.sort(intervals, new Comparator<Interval>(){

				@Override
				public int compare(Interval a, Interval b) {
					if(a.start < b.start) {
						return -1;
					} else if(a.start > b.start) {
						return 1;
					}
					return 0;
				}
	    	});
	    	int start=intervals.get(0).start, end=intervals.get(0).end;
	    	for(Interval it:intervals) {
	    		if(it.start <= end) {
	    			end = Math.max(it.end, end);
	    		} else {
	    			res.add(new Interval(start, end));
	    			start = it.start;
	    			end = it.end;
	    		}
	    	}
	    	res.add(new Interval(start, end));
	    	return res;
	    }

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

---

我的微信公众号