[数据结构与算法]leetcode刷题：贪心算法15（合并区间）

56. 合并区间

力扣题目链接

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

• 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
• 输出: [[1,6],[8,10],[15,18]]
• 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

• 输入: intervals = [[1,4],[4,5]]
• 输出: [[1,5]]
• 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
• 注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

提示：

• intervals[i][0] <= intervals[i][1]

先二维数组按第一列升序，第二列降序。
初始化第一个区间的开始和末尾，遍历下一个区间，如果这个区间的开始位置>end，使用map记录上一个区间的值（不可能重复，否则合并了）。更新最新的start和end。

package com.programmercarl.greed;

import com.programmercarl.util.GenerateArray;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName Merge
 * @Descriotion TODO
 * @Author nitaotao
 * @Date 2022/7/17 12:30
 * @Version 1.0
 * https://leetcode.cn/problems/merge-intervals/
 * 56. 合并区间
 **/
public class Merge {
    public int[][] merge(int[][] intervals) {
        HashMap<Integer, Integer> map = new HashMap<>();
        //排序，根据起始位置升序，按末尾位置降序
        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return Integer.compare(o2[1], o1[1]);
            } else {
                return Integer.compare(o1[0], o2[0]);
            }
        });
        int start = intervals[0][0];
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] > end) {
                //如果起始位置>end
                map.put(start, end);
                start = intervals[i][0];
                end = intervals[i][1];
            } else {
                //否则就取两者中右边界的最大值
                end = Math.max(end, intervals[i][1]);
            }
        }
        //最后一个单独设置为一组
        map.put(start, end);
        int[][] result = new int[map.size()][2];
        int n = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            result[n][0] = entry.getKey();
            result[n][1] = entry.getValue();
            n++;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(new Merge().merge((int[][]) GenerateArray.generateArrays("[[1,3],[2,6],[8,10],[15,18]]", "int")));
    }
}