986 区间列表的交集

一、题目

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

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

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

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

二、题解

思路：双指针法

我们可以使用两个指针 i 和 j，分别指向 firstList 和 secondList 中的当前遍历到的区间。 对于当前遍历到的两个区间 A = firstList[i] 和 B = secondList[j]：

  1. 判断是否有交集： 两个区间存在交集的条件是：两个区间起始端点的最大值，必须小于等于两个区间结束端点的最小值。 即：start = Math.max(A[0], B[0]) 且 end = Math.min(A[1], B[1])。 如果 start <= end，那么 [start, end] 就是它们的一个交集区间。
  2. 移动指针： 找到交集（或者没有交集）之后，我们需要移动指针。谁的右端点更小，就移动谁的指针。 为什么？因为当前区间右端点较小的那个，不可能再与对方列表里的下一个区间产生交集了（因为它已经结束了，而对方列表的区间还在继续或者向后推移）。
    • 如果 A[1] < B[1]，说明 firstList 的当前区间结束得早，指针 i++。
    • 否则，说明 secondList 的当前区间结束得早（或者同时结束），指针 j++。
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> ans = new ArrayList<>();
        int i = 0, j = 0;

        // 当两个列表都还没有遍历完时，继续循环
        while (i < firstList.length && j < secondList.length) {
            // 获取当前遍历到的两个区间的起点和终点
            int a1 = firstList[i][0], a2 = firstList[i][1];
            int b1 = secondList[j][0], b2 = secondList[j][1];

            // 计算可能交集的起点和终点
            int start = Math.max(a1, b1);
            int end = Math.min(a2, b2);

            // 如果 start <= end，说明有真实的交集
            if (start <= end) {
                ans.add(new int[]{start, end});
            }

            // 谁的右端点小，谁的指针向前移动一步
            if (a2 < b2) {
                i++;
            } else {
                j++;
            }
        }

        // 将 List 转换为二维数组返回
        return ans.toArray(new int[ans.size()][]);
    }
}

时间复杂度：O(M+N)O(M + N)

空间复杂度：O(1)O(1)

评论