1. 题⽬链接：56.合并区间

2. 题⽬描述：

3. 解法（排序+贪⼼）：

贪⼼策略：

a. 先按照区间的「左端点」排序：此时我们会发现，能够合并的区间都是连续的；

b. 然后从左往后，按照求「并集」的⽅式，合并区间。 

如何求并集：

由于区间已经按照「左端点」排过序了，因此当两个区间「合并」的时候，合并后的区间：

a. 左端点就是「前⼀个区间」的左端点；

b. 右端点就是两者「右端点的最⼤值」。

C++算法代码： 

class Solution
{
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals)
    {
        //初始化
        int n = intervals.size();
        if(n==1)
        {
            return intervals;
        }
        //排序
        sort(intervals.begin(), intervals.end());
        //建表
        vector<vector<int>>ret;
        //填表
        int min_num,max_num;
        for (int i = 0; i < n - 1;i++)
        {
            //临时存储参数
            min_num = intervals[i][0], max_num = intervals[i][1];
            while (i + 1 < n && intervals[i + 1][0] <= max_num)
            {
                min_num = min(min_num, intervals[i + 1][0]);
                max_num = max(max_num, intervals[i + 1][1]);
                i++;
            }
            ret.push_back({ min_num,max_num });
        }
        //处理最后一个
        if(max_num < intervals[n-1][0])
        {
            ret.push_back(intervals[n-1]);
        }
        return ret;
    }
};

Java算法代码：

class Solution
{
	public int[][] merge(int[][] intervals)
	{
		// 1. 按照左端点排序 
		Arrays.sort(intervals, (v1, v2) ->
		{
			return v1[0] - v2[0];
		});
		// 2. 合并区间 - 求并集 
		int left = intervals[0][0], right = intervals[0][1];
		List<int[]> ret = new ArrayList<>();
		for (int i = 1; i < intervals.length; i++)
		{
			int a = intervals[i][0], b = intervals[i][1];
			if (a <= right) // 有重叠部分 
			{
				// 合并 - 求并集 
				right = Math.max(right, b);
			}
			else // 不能合并 
			{
				ret.add(new int[] {left, right});
				left = a;
				right = b;
			}
		}
		// 别忘了最后⼀个区间 
		ret.add(new int[] {left, right});
		return ret.toArray(new int[0][]);
	}
}