区间合并

给定一组区间，合并所有重叠的间隔。

例如：
[1,3],[2,6],[8,10],[15,18]

返回：
[1,6],[8,10],[15,18]

   

    解决思路：

    首先我们需要创建一个区间类，类中属性为start和end并且实现排序，我们队排序后的区间类进行判断

    例如区间类为A ，我们需要循环区间类集合，比较两个区间类A1，A2如果A1.start>=A2.end则我们人A1,A2是可以合并的。

   

public class MergeIntervals implements Comparable<MergeIntervals> {

    private int start;// 时间间隔开始位置
    private int end;// 时间价格结束位置

    public MergeIntervals(int start, int end) {

        this.start = start;
        this.end = end;
    }

    public MergeIntervals() {
    }

    /**
     * 合并时间间隔
     * 
     * @param list 需要合并的时间间隔集合
     * @return 合并后的时间间隔集合
     */
    public List<MergeIntervals> merge(List<MergeIntervals> list) {

        // 最终要返回的结果集
        List<MergeIntervals> resluts = new ArrayList<MergeIntervals>();

        // 如果集合为空或者size小于等于1则无需合并
        if (list == null || list.size() <= 1) {
            return list;
        } else {
            // 首先对集合进行排序
            Collections.sort(list);
            // 取出list中的第一个间隔
            MergeIntervals pre = list.get(0);

            for (int i = 1; i < list.size(); i++) {
                // 取出当前的时间间隔
                MergeIntervals curr = list.get(i);

                // 如果前一个间隔的结束位置大于后一个间隔的开始位置说明两个间隔存在交叉，可以合并
                if (pre.end >= curr.start) {
                    pre = new MergeIntervals(pre.start, Math.max(pre.end, curr.end));
                } else {
                    // 否则不能合并
                    resluts.add(pre);
                    pre = curr;
                }

            }
            resluts.add(pre);
        }
        return resluts;
    }

    /**
     * 比较器 用于对集合中的时间间隔进行排序
     * 
     * @param o
     * @return
     * @see java.lang.Comparable#compareTo(java.lang.Object)
     */
    @Override
    public int compareTo(MergeIntervals o) {
        return this.start - o.start;
    }

    public static void main(String[] args) {

        MergeIntervals test = new MergeIntervals();
        List<MergeIntervals> list = new ArrayList<MergeIntervals>();
        MergeIntervals mergeIntervals = new MergeIntervals(1, 3);
        MergeIntervals mergeIntervals1 = new MergeIntervals(2, 6);
        MergeIntervals mergeIntervals2 = new MergeIntervals(8, 10);
        MergeIntervals mergeIntervals3 = new MergeIntervals(15, 18);
        list.add(mergeIntervals);
           list.add(mergeIntervals1);
           list.add(mergeIntervals2);
           list.add(mergeIntervals3);

        List<MergeIntervals> list2 = test.merge(list);

        for (MergeIntervals mm : list2) {
            System.out.println(mm.start + "--" + mm.end);
        }
    }
}