가장 쉽게 접근하기 위해서는 두 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
Approach
Idea: Two Pointer
가장 쉽게 접근하기 위해서는 두 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를 활용하여 다음과 같이 코드를 작성할 수 있다.Complexity
O(m + n)O(1)(res제외)