leetcode
leetcode 901 ~ 950
区间列表的交集

区间列表的交集

难度:

标签:

题目描述

给定两个由一些 闭区间 组成的列表，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

代码结果

运行时间: 32 ms, 内存: 17.0 MB

/*
 * 题目思路：
 * 与上面的Java解决方案类似，使用双指针和Java Stream API来处理。
 */
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public List<int[]> intervalIntersectionStream(int[][] firstList, int[][] secondList) {
    List<int[]> result = Arrays.stream(firstList)
        .flatMap(a -> Arrays.stream(secondList)
            .map(b -> new int[]{Math.max(a[0], b[0]), Math.min(a[1], b[1])})
            .filter(interval -> interval[0] <= interval[1]))
        .collect(Collectors.toList());
    return result;
}

解释

方法:

该题解采用了双指针技术遍历两个输入的区间列表。两个指针分别指向firstList和secondList的当前区间。通过比较两个当前区间的起始和结束位置来判断它们是否相交，并计算交集。如果一个区间的结束位置小于另一个区间的结束位置，则移动该区间的指针以检查下一个区间，否则移动另一个区间的指针。这样可以保证每个区间只被访问一次，直到一个列表的区间被全部访问完毕。

时间复杂度:

O(M+N)

空间复杂度:

O(min(M, N))

代码细节讲解

🦆
这种双指针技术为何能有效处理区间列表的交集问题？
▷
双指针技术在处理区间列表的交集问题时能够有效地提高算法的效率和减少不必要的比较。这种方法通过在两个列表上各自维护一个指针，只对当前的区间进行比较和处理，避免了对所有区间的全面比较。一旦确定两个区间是否相交，并处理完毕（例如记录交集），就可以根据区间的结束时间来决定移动哪一个指针。这样，每个区间最多被访问一次，从而减少了时间复杂度到线性级别，即O(n+m)，其中n和m是两个列表的长度。
🦆
算法如何确保在所有区间被正确处理的同时不会重复处理任何区间？
▷
算法通过逐步移动结束时间较早的区间的指针来确保每个区间只被处理一次而不会被重复处理。在每步操作中，只有当前比较的两个区间中结束时间较早的那个区间的指针会向前移动，这样可以保证每个区间在被比较后即被排除在后续的比较之外。这种方式有效地避免了对已经处理过的区间的重复处理，并确保了所有区间都会被逐个检查。
🦆
当存在一个区间完全包含另一个区间时，这种双指针方法是如何处理的？
▷
当一个区间完全包含另一个区间时，双指针方法仍然能够有效地计算交集。在这种情况下，被完全包含的区间与包含它的区间的交集实际上就是被包含区间本身。算法通过计算两个区间的最大起始点和最小结束点来确定交集区间。如果一个区间完全包含另一个，那么较小的区间（被包含者）的起始点和结束点会决定交集的边界。在这之后，结束时间较早的区间的指针将向前移动，以检查可能的新的交集区间。
🦆
在双指针遍历中，如果两个列表的长度差异很大，这种方法的效率如何？
▷
在双指针遍历中，即使两个列表的长度差异很大，该方法仍然是效率较高的。因为算法的时间复杂度主要依赖于较短的列表，因为一旦较短列表中的所有区间都被处理完，算法就会终止。这意味着算法的时间复杂度是O(min(n,m))，其中n和m分别是两个列表的长度。因此，即使其中一个列表特别长，只要另一个列表的长度较短，算法仍然能够快速地完成处理。

相关问题

合并区间

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

 

示例 1：

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

示例 2：

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

 

提示：

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

 

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

 

提示：

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[j] <= 109

 

进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

员工空闲时间

员工空闲时间
查询后的偶数和二叉树的垂序遍历