56. 合并区间 (中等)

Posted on In Views: 1

1，问题描述

56. 合并区间

难度：中等

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

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

示例 2：

1
2
3
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 10^4

2，初步思考

​ 解法 1：线段树

​ 使用 dp 缓存数据，去判断每个终点减起点的数据是否一致，如果是的那么说明已经被合并，否则就是还没有被合并

​ 解法 2：区间合并

​ 先利用有限队列排序，然后在依次进行比较合并区间，无法合并的区间就直接输出

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class _56合并区间 {

    // 解法：排序+双指针
    public int[][] merge_slip_gov(int[][] intervals) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
        for (int i = 0; i < intervals.length; i++) {
            queue.offer(intervals[i]);
        }

        List<int[]> temp = new ArrayList<>();
        int[] poll = queue.peek();
        int start = poll[0];
        int end = poll[1];
        while (!queue.isEmpty()) {
            poll = queue.poll();
            int startCur = poll[0];
            int endCur = poll[1];
            if (startCur <= end) {// 存在重叠区间
                end = Math.max(end, endCur);
            } else {// 不存在重叠区间
                int[] tempChild = new int[2];
                tempChild[0] = start;
                tempChild[1] = end;
                temp.add(tempChild);
                start = startCur;
                end = endCur;
            }
        }
        int[] tempChild = new int[2];
        tempChild[0] = start;
        tempChild[1] = end;
        temp.add(tempChild);

        int[][] res = new int[temp.size()][2];
        for (int i = 0; i < temp.size(); i++) {
            res[i] = temp.get(i);
        }
        return res;
    }


    // 解法：线段树
    public int[][] merge_tree(int[][] intervals) {
        int[] dp = new int[10002];
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
        for (int i = 0; i < intervals.length; i++) {
            queue.offer(intervals[i]);
        }

        while (!queue.isEmpty()) {
            int[] interval = queue.poll();
            int start = interval[0];// 起始点【闭区间】
            int end = interval[1];// 结束点【闭区间】
            if (start == end) {
                if (dp[start] != 0) continue;
                dp[start] = 1;
            }
            if (dp[end] - dp[start] == end - start) continue;// 已经被包含了

            int startCnt = dp[start];
            startCnt = startCnt == 0 ? 1 : startCnt;
            for (int j = start; j <= end; j++) {
                dp[j] = j - start + startCnt;
            }
        }

        List<int[]> temp = new ArrayList<>();
        for (int i = 1; i < dp.length; i++) {
            if (dp[i - 1] > 0 && dp[i] <= dp[i - 1]) {
                int[] tempChild = new int[2];
                tempChild[1] = i - 1;// 索引
                tempChild[0] = tempChild[1] - dp[i - 1] + 1;// 索引-长度
                temp.add(tempChild);
            }
        }
        int[][] res = new int[temp.size()][2];
        for (int i = 0; i < temp.size(); i++) {
            res[i] = temp.get(i);
        }
        return res;
    }

    public static void main(String[] args) {
        _56合并区间 merge = new _56合并区间();
        int[][] ints;
//        ints = merge.merge_tree(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}});
//        ints = merge.merge_tree(new int[][]{{1, 4}, {4, 5}});
//        ints = merge.merge_tree(new int[][]{{1, 4}, {5, 6}});
//        ints = merge.merge_tree(new int[][]{{1, 4}, {0, 0}});
        ints = merge.merge_tree(new int[][]{{1, 3}, {8, 10000}, {3, 8}});


        for (int i = 0; i < ints.length; i++) {
            System.out.print("[" + ints[i][0] + "," + ints[i][1] + "],");
        }
    }
}