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://oj.leetcode.com/problems/merge-intervals/

思路：先按照起始点排序，然后遍历合并即可。

代码：

import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;public class Solution {    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {        if (intervals == null)            return null;        Collections.sort(intervals, new Comparator<Interval>() {            public int compare(Interval a, Interval b) {                return a.start - b.start;            }        });        ArrayList<Interval> res = new ArrayList<Interval>();        int i;        for (i = 0; i < intervals.size();) {            int j = i + 1;            Interval merged = new Interval(intervals.get(i).start,                    intervals.get(i).end);            while (j < intervals.size()                    && isConnected(merged, intervals.get(j))) {                merged = merge(merged, intervals.get(j));                j++;            }            res.add(merged);            i = j;        }        return res;    }    private boolean isConnected(Interval a, Interval b) {        return (a.start >= b.start && a.start <= b.end)                || (b.start >= a.start && b.start <= a.end);    }    private Interval merge(Interval a, Interval b) {        int newStart = a.start < b.start ? a.start : b.start;        int newEnd = a.end > b.end ? a.end : b.end;        a.start = newStart;        a.end = newEnd;        return a;    }    public static void main(String[] args) {        // [1,3],[2,6],[8,10],[15,18]        Interval one = new Interval(2, 4);        Interval two = new Interval(1, 2);        Interval three = new Interval(4, 10);        Interval four = new Interval(10, 18);        ArrayList<Interval> intervals = new ArrayList<Interval>();        intervals.add(one);        intervals.add(two);        intervals.add(three);        intervals.add(four);        System.out.println(new Solution().merge(intervals));    }}

参考：

http://leetcodenotes.wordpress.com/2013/08/01/merge-intervals/