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

原问题链接：https://leetcode.com/problems/merge-intervals/

 

问题分析

　　这里需要将一组interval给合并起来。其实如果有一组interval它们的起始点start是递增的，我们可以通过取第一个开始，每次和后面的比较，如果后面那个interval和前面的没有交叉，则将前面的这个interval加入到结果集中，否则进行合并。而合并的流程比较简单，取两个interval中间end值大的那个。因为这里是按照start的顺序从小到大排列的，所以甚至可以不需要比较。

　　这样，在具体的实现里我们首先将给定的List按照start从小到大的排序，然后再按照前面描述的合并以及加入到结果集中。具体的实现如下：

 

/**
 * 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; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if(intervals.size() <= 1)
            return intervals;
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval t1, Interval t2) {
                return t1.start - t2.start;
            }
        });
        List<Interval> result = new ArrayList<Interval>();
        int curStart = intervals.get(0).start;
        int curEnd = intervals.get(0).end;
        for(int i = 1; i < intervals.size(); i++) {
            if(curEnd >= intervals.get(i).start) {
                curEnd = Math.max(curEnd, intervals.get(i).end);
                curStart = Math.min(curStart, intervals.get(i).start);
            } else {
                result.add(new Interval(curStart, curEnd));
                curStart = intervals.get(i).start;
                curEnd = intervals.get(i).end;
            }
        }
        result.add(new Interval(curStart, curEnd));
        return result;
    }
}

　　因为目前的实现已经支持java 8了，如果我们再运用一点lambda表达式语法的技巧， 代码可以更加简略一点：

 

public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if(intervals.size() <= 1)
            return intervals;
        Collections.sort(intervals, (t1, t2) -> t1.start - t2.start);
        List<Interval> result = new ArrayList<Interval>();
        int curStart = intervals.get(0).start;
        int curEnd = intervals.get(0).end;
        for(int i = 1; i < intervals.size(); i++) {
            if(curEnd >= intervals.get(i).start) {
                curEnd = Math.max(curEnd, intervals.get(i).end);
                curStart = Math.min(curStart, intervals.get(i).start);
            } else {
                result.add(new Interval(curStart, curEnd));
                curStart = intervals.get(i).start;
                curEnd = intervals.get(i).end;
            }
        }
        result.add(new Interval(curStart, curEnd));
        return result;
    }
}