9、区间重合判断

时间:2024-03-14 07:38:40

区间重合判断
给你一个target线段,判断它是否被已给出的一些线段所包含。

先排序,再将目标区间合并为一个或多个更大的区间,最后判断这些大区间是否可以覆盖源区间。
排序使用快速排序,排序后进行合并,例如比较y0和x1的大小可以判断两个相邻的目标区间是否有交集,如果有交集合并为一个大的区间。
最后再查找,看是否有满足 x <= xi && y <=yi 的目标区间,有的话则可以判定为覆盖。

算法复杂度:
排序采用快速排序的方式:O(N*Log2(N))
合并遍历一次目标区间 : O(N)
查找遍历一次目标区间 : O(N)

9、区间重合判断