LeetCode986. 区间列表的交集

本文最后更新于 484 天前，其中的信息可能已经有所发展或是发生改变。

一、思路

这个区间问题，在两个列表里，互相比较。采用双指针是实现这个过程。

分为两种情况，相交和不相交。相交情况，end取两个区间的最大值。不相交时，看哪个区间大，当前的end是小的区间的最大值。下一对start，end取大的个区间。

什么时候指针移动呢？根据两个当前区间的最大值，小的个指针就往前移。因为一直在进行两个区间的比较，所以趋向于两个指针一起往前走。

二、问题

给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。

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

形式上，闭区间[a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。

两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

示例 1：

输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

复制

示例 2：

输入：firstList = [[1,3],[5,9]], secondList = []
输出：[]

复制

示例 3：

输入：firstList = [], secondList = [[4,8],[10,12]]
输出：[]

复制

示例 4：

输入：firstList = [[1,7]], secondList = [[3,10]]
输出：[[3,7]]

复制

提示：

• 0 <= firstList.length, secondList.length <= 1000
• firstList.length + secondList.length >= 1
• 0 <= starti < endi <= 109
• endi < starti+1
• 0 <= startj < endj <= 109
• endj < startj+1

Related Topics

• 双指针

\n

• 132
• 0

三、代码

public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
            ArrayList<int[]> list = new ArrayList<>();
            int pointer = 0;
            int pointer1 = 0;
            while (pointer < firstList.length && pointer1 < secondList.length) {
                int n1 = Math.min(firstList[pointer][1], secondList[pointer1][1]);
                int n0 = Math.max(firstList[pointer][0], secondList[pointer1][0]);
                if (n1 >= n0) {
                    list.add(new int[]{n0, n1});
                }
                if (firstList[pointer][1] > secondList[pointer1][1]) {
                    pointer1++;
                } else {
                    pointer++;
                }
            }
            return list.toArray(new int[list.size()][]);
        }

复制

Post Views: 260