[LC] 986. Interval List Intersections

[seungriyou]

986. Interval List Intersections (similar to #116)

Approach

Idea: Two Pointer

ref: https://leetcode.com/problems/interval-list-intersections/solutions/647482/python-two-pointer-approach-thinking-process-diagrams

가장 쉽게 접근하기 위해서는 두 interval 간에 발생할 수 있는 모든 관계를 그림으로 그려보는 것이다.

• 그림을 그려보면 두 interval [s1, e1], [s2, e2]가 서로 겹치는 경우는 (s1 > e2 || e1 < s2) 인 경우에 해당하지 않을 때라는 것을 알 수 있다.

  ➡️ 즉, (s1 <= e2 && e1 >= s2) 인 경우라면 겹치는 것이다!

• 또한, 겹치는 interval의 구간은 [max(s1, s2), min(e1, e2)] 가 된다는 것도 알 수 있다.

따라서 두 interval에 대한 two pointer i, j를 활용하여 다음과 같이 코드를 작성할 수 있다.

i = j = 0
res = []

while i < len(firstList) and j < len(secondList):
    s1, e1 = firstList[i]
    s2, e2 = secondList[j]

    # 두 interval이 겹치는 경우
    if s1 <= e2 and e1 >= s2:
        # 겹치는 구간 기록
        res.append([max(s1, s2), min(e1, e2)])
    
    # [s1, e1]과 [s2, e2] 중 e가 큰쪽을 다음 단계에도 더 살펴보아야 함
    if e1 <= e2:
        i += 1
    else:
        j += 1

return res

Complexity

• Time: O(m + n)
• Space: O(1) (res 제외)