编程题：合并区间

给出一个区间的集合，请合并所有重叠的区间。
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

public class MySet {
    int left;
    int right;

    public MySet(){

    }

    public MySet(int left,int right){
        this.left = left;
        this.right = right;
    }

    public int getLeft() {
        return left;
    }

    public void setLeft(int left) {
        this.left = left;
    }

    public int getRight() {
        return right;
    }

    public void setRight(int right) {
        this.right = right;
    }
}

解法：

   public static  List<MySet> mergeSet(List<MySet> theSets) {

        if (theSets == null || theSets.size() <= 1) {
            return theSets;
        }
        List<MySet> result = new ArrayList<>();


        theSets.sort((set1,set2)->{
            return set1.getLeft() - set2.getLeft();
        });

        MySet mySet = theSets.get(0);
        for (int i = 1; i < theSets.size(); i++){
            if (!(mySet.getRight() < theSets.get(i).getLeft())){
                mySet.setRight(Math.max(mySet.getRight(),theSets.get(i).getRight()));
            } else {
                result.add(mySet);
                mySet = theSets.get(i);
            }
        }
        //最后一定要将最后合并的元素加入到结果中。否则会丢失元素。
        result.add(mySet);

        return result;
    }



   public static void main(String[] args) {
        MySet mySet1 = new MySet(1,4);
        MySet mySet2 = new MySet(2,6);
        MySet mySet3 = new MySet(8,10);
        MySet mySet4 = new MySet(12,13);
        MySet mySet5 = new MySet(16,19);

        List<MySet> mySets = new LinkedList<>();
        mySets.add(mySet1);
        mySets.add(mySet2);
        mySets.add(mySet3);
        mySets.add(mySet4);
        mySets.add(mySet5);
        List<MySet> result = mergeSet(mySets);
        System.out.println(JSONObject.toJSONString(result));
    }

输出结果：

[{"left":1,"right":6},{"left":8,"right":10},{"left":12,"right":13},{"left":16,"right":19}]