Skip to content

Latest commit

 

History

History
5 lines (3 loc) · 491 Bytes

File metadata and controls

5 lines (3 loc) · 491 Bytes

986.Interval-List-Intersections

本题中的两个区间序列都已经有序了,所以不需要扫描线算法,可以直接双指针。

用i和j分别指向当前两个序列的第一个区间。如果这两个区间完全不相交,那么将区间更早的那个序列指针增1。如果这两个区间有相交的部分,那么就收录相交的部分{max(s1,s2), min(e1,e2)},然后依然将区间更早的那个序列指针增1。直至某个序列的指针越界。