题目地址：

https://leetcode.com/problems/merge-intervals/

给定一列区间，合并完成后返回。

法1：排序后逐个merge。先将区间按照左端点排序，如果左端点相等就右端点小的在前面，然后从左到右扫描这些区间。每次扫描的时候，都check一下这个区间的start是不是小于上一个区间的end，如果小于，说明可以合并，这时更新end；否则说明不能合并，那就把下一个区间加进答案里。遍历完后返回。代码如下：

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return intervals;
        }
    	// 按左端点排序，如果左端点一样就谁右端点小排前面
        Arrays.sort(intervals, (i1, i2) -> {
            if (i1[0] != i2[0]) {
                return i1[0] < i2[0] ? -1 : 1;
            } else {
                if (i1[1] != i2[1]) {
                    return i1[1] < i2[1] ? -1 : 1;
                } else {
                    return 0;
                }
            }
        });
        
        List<int[]> list = new ArrayList<>();
        list.add(intervals[0]);
        // 每次新遍历到一个区间，就尝试将其merge进list中
        for (int i = 1; i < intervals.length; i++) {
            mergeLast(list, list.get(list.size() - 1), intervals[i]);
        }
        
        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
	
	private void mergeLast(List<int[]> list, int[] last, int[] cur) {
		// 如果last和cur不相交，则直接将cur加进list；否则拓宽last右端点
        if (last[1] < cur[0]) {
            list.add(cur);
        } else {
            last[1] = Math.max(last[1], cur[1]);
        }
    }
}

时间复杂度$O(n\log n)$，因为要排序，空间$O(n)$。

法2：可以开一个新的class，表示每一个区间的端点，不仅记录其坐标，也要记录一下其是否是左端点。并且对这个class规定一个偏序关系，坐标不等则坐标左者在前，否则的话是左端点者在前。容易证明这个关系确实是个偏序关系。接着对这些点排好序，然后遍历这些点，直到凑成一个“括号”（凑成一个括号的意思是，左端点的点数目和右端点相等了）的时候，说明一部分区间合并完毕，则加入最终结果中。代码如下：

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

public class Solution {
    class Point implements Comparable<Point> {
        int x;
        boolean isLeft;
        
        Point(int x, boolean isLeft) {
            this.x = x;
            this.isLeft = isLeft;
        }
        
        @Override
        public int compareTo(Point another) {
            if (this.x != another.x) {
                return this.x < another.x ? -1 : 1;
            }
            
            return this.isLeft ? -1 : 1;
        }
    }
    
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return intervals;
        }
        
        TreeSet<Point> set = new TreeSet<>();
        for (int[] interval : intervals) {
            set.add(new Point(interval[0], true));
            set.add(new Point(interval[1], false));
        }
        
        List<int[]> list = new ArrayList<>();
        int leftCount = 0, left = Integer.MAX_VALUE;
        for (Point point : set) {
            if (point.isLeft) {
                left = Math.min(left, point.x);
                leftCount++;
            } else {
                leftCount--;
                if (leftCount == 0) {
                    list.add(new int[]{left, point.x});
                    left = Integer.MAX_VALUE;
                }
            }
        }
        
        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        
        return res;
    }
}

时间复杂度$O(n\log n)$，空间$O(n)$。