区间合并相关问题

发表于 分类于 Artalk： loading...
有序集合 设计

总结一下乐扣上「合并区间」相关的题目

主体思路很简单，使用有序集合，Java语言下对应TreeMap，来保存区间（key:左端点，value:右端点）。在插入的过程中进行区间的合并、分裂以及相关计算。

关于TreeMap这个工具类，主要用到floorKey/ceilingKey、lowerKey/higherKey方法，注意区别，一个是取闭区间，一个是取开区间

官方文档

image-20230106174921275

image-20230106174855403

下面是题单

56. 合并区间

题目描述

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

示例

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

分析

最直观的思路，维持两个变量curLeft和curRight，记录当前上一个区间的左端点和右端点。每当插入新区间[l,r]

  • 如果l > curRight，说明区间无交集，将上一个区间放入结果集，更新curLeft和curRight；

  • 如果l <= curRight，说明当前区间和上一个区间有交集，合并两个区间。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        Arrays.sort(intervals, (a,b)->a[0] - b[0]);
        int curLeft = intervals[0][0], curRight = intervals[0][1];
        int n = intervals.length;
        for (int i = 1; i < n; ++i) {
            int l = intervals[i][0], r = intervals[i][1];
            if (l <= curRight) {
                curRight = Math.max(curRight, r);
                // curLeft = Math.min(curLeft, l); // 有序性保证了curLeft一定小于l，无须更新curLeft
            }
            else {
                res.add(new int[]{curLeft, curRight});
                curLeft = l; curRight = r;
            }
        }
        res.add(new int[]{curLeft, curRight});
        int[][] ans = new int[res.size()][2];
        int idx = 0;
        for (int[] x : res) ans[idx++] = new int[]{x[0], x[1]};
        return ans;
    }
}

本文将介绍的思路如下

将每个区间用键值对的形式保存到TreeMap中，其中键是左端点，值为右端点，所有的区间会按照左端点进行排序

每当插入一个新区间 [l,r]，先在集合中寻找与之有交集的区间 [L, R]，如何确保有交集呢？

  • 首先寻找左端点小于等于新区间右端点r的区间，L = floorKey(r)

  • 还要保证右端点R要大于等于新区间的左端点l

  • 最后合并区间，更新l，r

循环以上过程，直到找不出和 [l, r] 有交集的区间

以下列出有交集的四种情况

leetcode-56-intervals-merge

代码实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
TreeMap<Integer, Integer> mp = new TreeMap<>();
for (int[] t : intervals) {
    int l = t[0], r = t[1];
    Integer L = mp.floorKey(t[1]);
    while (L != null && mp.get(L) >= l) {
        // 更新 l , r
        l = Math.min(l, L);
        r = Math.max(r, mp.get(L));
        mp.remove(L); // 移除原区间
        L = mp.floorKey(r); // 继续寻找有交集的区间[L, R]
    }
    mp.put(l, r);
}

完整代码

题目描述

image-20230106181421446

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[][] merge(int[][] intervals) {
        TreeMap<Integer, Integer> mp = new TreeMap<>();
        for (int[] t : intervals) {
            int l = t[0], r = t[1];
            Integer L = mp.floorKey(t[1]);
            while (L != null && mp.get(L) >= l) {
                // 更新 l , r
                l = Math.min(l, L);
                r = Math.max(r, mp.get(L));
                mp.remove(L); // 移除原区间
                L = mp.floorKey(r); // 继续寻找有交集的区间[L, R]
            }
            mp.put(l, r);
        }
        int[][] ans = new int[mp.size()][2];
        int idx = 0;
        for (var entry : mp.entrySet()) {
            ans[idx++] = new int[]{ entry.getKey(), entry.getValue()};
        }
        return ans;
    }
}

57. 插入区间

给你一个 无重叠的，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

与56题十分类似

最优解

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
class Solution {
    public int[][] insert(int[][] inter, int[] nn) {
        List<int[]> ans = new ArrayList<>();
        int left = nn[0], right = nn[1];
        boolean tag = false;
        for (int[] x : inter) {
            // 如果无交集，并且[left,right] 在当前区间之前
            if (x[0] > right) { 
                if (!tag) {
                    ans.add(new int[]{left, right});
                    tag = true;
                }
                ans.add(x);
            } else if (x[1] < left) ans.add(x); // 无交集，且在当前区间之后
            else {
                // 存在交集，更新left，right
                left = Math.min(left, x[0]);
                right = Math.max(right, x[1]);
            }
        }
        if (!tag) ans.add(new int[]{left, right});
        int[][] res = new int[ans.size()][2];
        for (int i = 0; i < ans.size(); ++i) {
            res[i] = ans.get(i);
        }
        return res;
    }
}

使用TreeMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[][] insert(int[][] intervals, int[] x) {
        TreeMap<Integer, Integer> mp = new TreeMap<>();
        for (int[] t : intervals) {
            mp.put(t[0], t[1]);
        }
        int l = x[0], r = x[1];
        Integer L = mp.floorKey(r);
        while (L != null && mp.get(L) >= l) {
            l = Math.min(l, L);
            r = Math.max(r, mp.get(L));
            mp.remove(L);
            L = mp.floorKey(r);
        }
        mp.put(l, r);
        int[][] ans = new int[mp.size()][2];
        int idx = 0;
        for (var entry : mp.entrySet()) {
            ans[idx++] = new int[]{entry.getKey(), entry.getValue()};
        }
        return ans;
    }
}

715. Range 模块

题目描述

image-20230106182434776

简要分析

包括区间合并和分裂，主体思路不变，根据具体情况判断即可。可以画图辅助思考

值得注意的是，本题使用的是左闭右开区间 [left,right)[\text{left}, \text{right})

添加区间时，将重叠的部分合并即可

查询区间时

image-20230106185408512

主要是removeRange(l, r)，需要分情况讨论

情况1:

image-20230106184841443

删去重叠部分后，留下区间 [r, R)

情况2:

image-20230106184854918

原区间分裂出两个区间，[L, l)和[r, R)

另外，如果R <= r的话，区间[r, R)也会被删除，这里就不再画图列出

代码实现

1
2
3
4
5
6
7
8
9
10
11
public void removeRange(int l, int r) {
    Integer L = mp.lowerKey(r);
    while (L != null && mp.get(L) > l) {
        Integer R = mp.get(L);
        if (L >= l) mp.remove(L);
        else mp.put(L, l);

        if (R > r) mp.put(r, R);
        L = mp.lowerKey(r);
    }
}

完整代码

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
class RangeModule {
    TreeMap<Integer, Integer> mp;
    public RangeModule() {
        this.mp = new TreeMap<>();
    }
    
    public void addRange(int l, int r) {
        Integer L = mp.floorKey(r);
        while (L != null && mp.get(L) >= l) {
            l = Math.min(l, L);
            r = Math.max(r, mp.get(L));
            mp.remove(L);
            L = mp.floorKey(r);
        }
        mp.put(l, r);
    }
    
    public boolean queryRange(int left, int right) {
        Integer L = mp.floorKey(left);
        return L != null && mp.get(L) >= right;
    }
    
    public void removeRange(int l, int r) {
        Integer L = mp.lowerKey(r);
        while (L != null && mp.get(L) > l) {
            Integer R = mp.get(L);
            if (L >= l) mp.remove(L);
            else mp.put(L, l);

            if (R > r) mp.put(r, R);
            L = mp.lowerKey(r);
        }
    }
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule obj = new RangeModule();
 * obj.addRange(left,right);
 * boolean param_2 = obj.queryRange(left,right);
 * obj.removeRange(left,right);
 */

2276. 统计区间中的整数数目

题目描述

image-20230106185646473

简要分析

用一个变量，记录所有不重叠区间的长度和，这即为count()所求的结果

每次插入新区间，发生重叠时，先减去原区间[L,R]的长度，再逐渐合并区间，直到没有区间与之存在交集。此时将新区间[l,r]的长度记录到结果集中即可。

完整代码

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
class CountIntervals {
    TreeMap<Integer, Integer> mp;
    int ans;
    public CountIntervals() {
        this.mp = new TreeMap<>();
        this.ans = 0;
    }
    
    public void add(int left, int right) {
        Integer L = mp.floorKey(right);
        int l = left, r = right;
        while (L != null && mp.get(L) >= l) {
            l = Math.min(l, L);
            r = Math.max(r, mp.get(L));
            ans -= (mp.get(L) - L + 1);
            mp.remove(L);
            L = mp.floorKey(r);
        }
        ans += (r - l + 1);
        mp.put(l, r);
    }
    
    public int count() {
        return ans;
    }
}