检查两个时间间隔数组是否重叠的优化解决方案？

Question

你能否找到两个时间间隔数组是否重叠，以一种优化的方式？假设输入数组A包含10个元素，每个元素都有一个开始日期和结束日期，类似地，输入数组B包含4个元素，每个元素都有一个开始数据和结束数据。现在找出A和B是否重叠？

示例1:

输入：

A={[1,5],[7,10],[11,15]}; //Array A contains 3elements, and each element have start and end time.
B={[6,10],[1,5]};//Array B contains 2elements, and each element have start and end time.

输出：是//为什么因为A和B在6,10 \x，1,5处重叠

示例2:

Input

A={[1,5],[8,10],[11,15]}; //Array A contains 3elements, and each element have start and end time.
B={[5,8],[15,16]};//Array B contains 2elements, and each element have start and end time.

输出： No //为什么因为A和B不重叠，在5,8，x，15,16处重叠

我知道我们可以用蛮力来解决这个问题，通过迭代B中的每个元素，并与A中的每个元素进行比较，来检查是否重叠(Ai.start<=Bj.start和Ai.end>Bj.start)，其中N是数组A的长度，M是B的长度，则需要O(N*M)。

你能优化一下解决方案吗。

Answer 1

您可以根据开始时间对数组进行排序。然后，通过同时迭代两个数组(使用两个指针)，可以检查元素的结束时间是否大于下一个元素的开始时间。如果是这样的话，那么您已经发现了一个重叠。

Answer 2

这里是你能做的

1. 使用数组A的值构建一个段树。如果第一个间隔id (l1，r1)，第二个是(l2，r2)等等。
2. 对于A(li，ri)中的每个间隔，更新段树，以便我们将区间(li，ri)中的每个元素更新为1。这可以在O(logn)中使用惰性传播来完成。
3. 现在，对于B(lj，rj)中的每个间隔，请尝试查询此范围的段树。查询将返回范围的和(lj，rj)。
4. 如果和为0，则该范围是不重叠的。否则它是重叠的

总复杂度O(nlogn)