解决方案


方法一:归并区间

思路

对于一个区间 [a, b],我们称 b 为末端点。

在两个数组给定的所有区间中,考虑拥有最小末端点的区间 A[0]。(为了不失一般性,假设 A[0]出现在数组 A 中)

然后,在数组 B 的区间中, A[0] 只可能与数组 B 中的至多一个区间相交。(如果 B 中存在两个区间均与 A[0] 相交,那么它们将共同包含 A[0] 的末端点,但是 B 中的区间应该是不相交的,所以导出矛盾)

算法

如果 A[0] 拥有最小的末端点,那么它只可能与 B[0] 相交。然后我们就可以删除区间 A[0] 了,因为它不能与其他任何区间再相交了。

相似的,如果 B[0] 拥有最小的末端点,那么它只可能与区间 A[0] 相交,然后我们就可以将 B[0] 删除了,因为它无法再与其他区间相交了。

我们用两个指针 ij 来虚拟地完成删除 A[0]B[0] 的操作。

复杂度分析

  • 时间复杂度:,其中 分别是数组 AB 的长度。

  • 空间复杂度:,也是答案区间数量的上限。