BM89 题解 | #合并区间#

看见进步： Good job！

这道题本来是感觉自己做不出来的，应该不行的，突然，画了一下图，就是一个区间排序，就跟游戏一样，有重合的判断，不就可以了吗？之后就自己做出来了。

还有跟值得骄傲自豪的是，我居然把快排也实现了，没有用系统的快排方法，太牛逼了！

解题思路：

1、给区间排序，

2、判断区间重合，若是合并，删除上一个加入新的，若否，直接添加

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param intervals Interval类ArrayList 
     * @return Interval类ArrayList
     */
    public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<Interval>();
        if(intervals == null || intervals.size()==0) {
            return res;
        }

        // List<Interval> sorts = quickSort(intervals);
        Collections.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval o1, Interval o2) {
                if(o1.start != o2.start) 
                    return o1.start - o2.start;
                else 
                    return o1.end - o2.end;
            }
        });
        int size = intervals.size();
        res.add(intervals.get(0));
        for(int i=1; i<size; i++) {
            Interval i1 = res.get(res.size()-1);
            Interval i2 = intervals.get(i);
            if(isIntervalContain(i1, i2)){
                res.remove(res.size()-1);
                res.add(mergeInterval(i1, i2));
            } else {
                 res.add(i2);
            }
        }

        return res;
    }

    boolean isIntervalContain(Interval i1, Interval i2) {
        if(i2.start <= i1.end) {
            return true;
        }
        return false;
    }

    Interval mergeInterval(Interval i1, Interval i2) {
        int start = i1.start <= i2.start ? i1.start: i2.start;
        int end = i1.end <= i2.end ? i2.end : i1.end;
        return new Interval(start, end);
    }


    /**
     *  我自己写的快排算法
     */
    List<Interval> quickSort(List<Interval> datas) {
        if(datas==null || datas.size()==1) {
            return datas;
        }

        int low = 0; 
        int high = datas.size();
        int mid = (high - low)/2;
        List<Interval> leftDatas = datas.subList(low, mid);
        List<Interval> rightDatas = datas.subList(mid, high);
        return merge(quickSort(leftDatas), quickSort(rightDatas));
    }

    ArrayList<Interval> merge(List<Interval> d1, List<Interval> d2) {
        ArrayList<Interval> res = new ArrayList<Interval>();
        int i1 = 0, i2 = 0;
        while(i1< d1.size() && i2<d2.size()) {
            Interval iv1 = d1.get(i1);
            Interval iv2 = d2.get(i2);
            if(iv1.start < iv2.start) {
                res.add(iv1);
                i1++;
            } else {
                res.add(iv2);
                i2++;
            }
        }

        while(i1 < d1.size()) {
            res.add(d1.get(i1));
            i1++;
        }

        while(i2 < d2.size()) {
             res.add(d2.get(i2));
             i2++;
        }

        return res;
    }

}