🌗 56. 合并区间

难度: 🌗

问题描述

---

解法

class Solution {
    public int[][] merge(int[][] intervals) {
        // 思路：
        // 根据 from 升序，然后每次遇到重叠区间进行合并，遇到不重叠区间将前面的区间添加到 res
        int len = intervals.length;
        List<int[]> res = new ArrayList<>();
        Arrays.sort(intervals, (a, b) -> {
            if(a[0] == b[0]) {
                return a[1] - b[1];
            } else {
                return a[0] - b[0];
            }
        });
        int min = intervals[0][0];
        int max = intervals[0][1];
        for(int i = 1; i < len; i ++) {
            int[] cur = intervals[i];
            int from = cur[0];
            int to = cur[1];
            // System.out.println(min + "  " + max  + "  " + from + "  " + to);
            if(max >= from) {
                // 可以合并区间
                max = Math.max(max, to);
            } else {
                // 可以添加到 res
                int[] tmp = new int[] {min, max};
                res.add(tmp);
                min = from;
                max = to;
            }
        }
        int[] tmp2 = new int[] {min, max};
        res.add(tmp2);
        int size = res.size();
        int[][] ans = new int[size][2];
        for(int i = 0; i < size; i ++) {
            ans[i] = res.get(i);
        }
        return ans;
    }
}

---

输出