LeetCode986-区间列表的交集

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/interval-list-intersections/

中文链接：https://leetcode-cn.com/problems/interval-list-intersections/

题目详述

给定两个由一些闭区间组成的列表，每个区间列表都是成对不相交的，并且已经排序。

返回这两个区间列表的交集。

（形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b。两个闭区间的交集是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3]。）

示例：

img

1
2
3
输入：A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
注意：输入和所需的输出都是区间对象组成的列表，而不是数组或列表。

提示：

  1. 0 <= A.length < 1000
  2. 0 <= B.length < 1000
  3. 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

题目详解

  • 运用双指针进行扫描。
  • 指针 i 指向 A， 指针 j 指向 B。
  • 如果 A[i][1] < B[j][0]，说明两者不相交，指针 i 右移。
  • 如果 B[j][1] < A[i][0]，说明两者不相交，指针 j 右移。
  • 上述两种情况都不满足说明两者相交，相交区间为 [max(A[i][0], B[j][0]), min(A[i][1], B[j][1])]。且在前面的区间没有再与其他区间相交的可能，对应的指针右移。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LeetCode_00986 {

    public int[][] intervalIntersection(int[][] A, int[][] B) {
        List<int[]> res = new ArrayList<>();
        int m = A.length, n = B.length;
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (A[i][1] < B[j][0]) {
                ++i;
            } else if (B[j][1] < A[i][0]) {
                ++j;
            } else {
                res.add(new int[] {Math.max(A[i][0], B[j][0]), Math.min(A[i][1], B[j][1])});
                if (A[i][1] < B[j][1]) {
                    ++i;
                } else {
                    ++j;
                }
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}