LeetCode(Sorting&Searching)Merge Intervals

2018-07-03

Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:

1
2
3

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

1
2
3

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considerred overlapping.

思路：想到了先给这些线段做一个排序，按左端点的大小排序，这样就可以将形如1-4, 0-2, 3,5这样的线段集合排序为0-2, 1-4, 3-5。这样就方便我们做merge，考虑这样的情况，只有在前一个线段的右端点大于等于后一个线段的左端点时才做merge, 但是要注意这时候还需要分两种情况：如果前一个线段的右端点大于等于后一个线段的右端点，那么说明后面的这个线段完全包含于前边的线段，这样就只需要将后面的这个线段remove掉，反之我们只需要将前一个线段的后端点设置为后一个线段的后端点，然后remove掉后面的这个线段即可。

代码如下：

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        Collections.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval o1, Interval o2){
                return (o1.start-o2.start);
            }
        });
        List<Interval> res=new ArrayList<Interval>();
        if(intervals.size()==1){
            return intervals;
        }
        int i=0;
        while(i<intervals.size()) {
        	while(i<intervals.size()-1 && intervals.get(i).end>=intervals.get(i+1).start) {
        		if(intervals.get(i).end>=intervals.get(i+1).end) {
        			intervals.remove(intervals.get(i+1));
        		}else {
        			intervals.get(i).end=intervals.get(i+1).end;
        			intervals.remove(intervals.get(i+1));
        		}
        	}
        	i++;
        }
        
        return intervals;
    }
}