56.md

#56. Merge Intervals 题目链接

思路：一个区间可以看成数字和两个数字之间的连续，将所有的数字乘以2，这样所有的数字一定是偶数，两个偶数之间的奇数看做是是否连续的标志位。一次遍历所有的区间，将区间的数字和连续位填入一个hashset中，然后对HashSet进行排序，然后将连续的区间输出。

public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        HashSet<Integer> all = new HashSet<>();
        intervals.forEach(interval -> {for (int i = interval.start; i < interval.end; i++)
                                    {
                                        all.add(2*i);
                                        all.add(2*i+1);
                                    }
                                    all.add(2*interval.end);
        });
        List<Integer> a = all.stream().sorted().collect(Collectors.toList());
        List<Interval> result = new ArrayList<>();
        for (int i = 0; i < a.size(); i++) {
            int start = a.get(i) / 2;
            while (i+1<a.size() && a.get(i+1)-a.get(i) == 1) {
                i++;
            }
            int end = a.get(i) / 2;
            result.add(new Interval(start, end));
        }
        return result;
    }
}

一种较快的方法，首先按照所有区间的start进行排序，然后按照顺序遍历区间，如果一个区间的start比上一个区间的end大，说明无法合并，那么将前一个区间就是一个已经合并好的区间。如果start比上一个区间的end小，那么说明可以合并，比较两个区间较大的end作为合并区间的end

public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> result = new ArrayList<>();
        if (intervals.size() == 0)
            return result;
        Collections.sort(intervals, (i1, i2) -> i1.start - i2.start);
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (Interval interval : intervals) {
            if (interval.start > end) {
                result.add(new Interval(start, end));
                start = interval.start;
                end = interval.end;
            }
            else {
                if (interval.end > end)
                    end = interval.end;
            }
        }
        result.add(new Interval(start, end));
        return result;
    }
}