개요
다음과 같이 두 개의 범위가 있다고 할 때,
├───A───┤
├───B───┤두 범위에 서로 겹치는 부분이 있는지, 없는지 판단하고 싶다. 간단한 방법이 있는지 알아본다.
경우의 수
서로 다른 두 개의 범위가 위치할 수 있는 경우의 수부터 알아보자.
1. 범위 A의 최댓값이 범위 B의 최솟값보다 작은 경우
max(A) < min(B) 또는 A_end < B_start 등으로 표현할 수 있다.
├───A───┤
├───B───┤
2. 범위 A의 최대값이 범위 B의 최솟값보다 크거나 같으면서 범위 B의 최댓값보다 작거나 같은 경우
min(B) <= max(A) <= max(B) 또는 B_start <= A_end <= B_end로 표현할 수 있다.
├───A───┤
├───B───┤
3. 범위 A의 최소값이 범위 B의 최솟값보다 크거나 같으면서 범위 B의 최댓값보다 작거나 같은 경우
min(B) <= min(A) <= max(B) 또는 B_start <= A_start <= B_end로 표현할 수 있다.
├───A───┤
├───B───┤
4. 범위 A의 최소값이 범위 B의 최댓값보다 큰 경우
min(A) > max(B) 또는 A_start > B_end 등으로 표현할 수 있다.
├───A───┤
├───B───┤
크게 위와 같이 네 가지 경우로 구분할 수 있을 것 같다.
+ 경계값에 대한 처리는 경우에 따라 다르게 해야 할 것 같다.
정리
두 범위가 겹치지 않는 조건은 다음과 같이 정리할 수 있다.
max(A) < min(B) OR min(A) > max(B)이 부분은 드모르간의 법칙에 의해 다음과 같이 정리할 수도 있다.
NOT (max(A) >= min(B) AND min(A) <= max(B))따라서 이 조건을 만족하면 두 범위는 겹치지 않고, 만족하지 않으면 겹치는 것으로 판단할 수 있다.
더 압축적으로 표현하면, 두 범위의 최솟값 중 큰 값이 두 범위의 최댓값 중 작은 값보다 작으면 두 범위는 겹치는 것으로 판단할 수 있다.
max(A_start, B_start) <= min(A_end, B_end)
테스트
다음과 같은 Python 함수로 두 범위가 겹치는지 확인해보자.
def is_overlaped(A, B):
return max(min(A), min(B)) <= min(max(A), max(B))
1. 범위 A의 최댓값이 범위 B의 최소값보다 작은 경우
A = range(1, 4)
B = range(5, 6)
print(f'A: {list(A)}, B: {list(B)}, {is_overlaped(A, B)}')
2. 범위 A의 최댓값이 범위 B의 최소값과 같은 경우
A = range(1, 6)
B = range(5, 8)
print(f'A: {list(A)}, B: {list(B)}, {is_overlaped(A, B)}')
3. 범위 A의 최대값이 범위 B의 최솟값보다 크면서 범위 B의 최댓값보다 작은 경우
A = range(3, 6)
B = range(4, 8)
print(f'A: {list(A)}, B: {list(B)}, {is_overlaped(A, B)}')
4. 범위 A의 최솟값이 범위 B의 최소값보다 크면서 범위 B의 최대값보다 작은 경우
A = range(3, 7)
B = range(1, 6)
print(f'A: {list(A)}, B: {list(B)}, {is_overlaped(A, B)}')
5. 범위 A의 최솟값이 범위 B의 최대값과 같은 경우
A = range(3, 5)
B = range(2, 4)
print(f'A: {list(A)}, B: {list(B)}, {is_overlaped(A, B)}')
6. 범위 A의 최소값이 범위 B의 최댓값보다 큰 경우
A = range(3, 7)
B = range(1, 2)
print(f'A: {list(A)}, B: {list(B)}, {is_overlaped(A, B)}')
참고 문서
https://circle-square.tistory.com/6
https://qastack.kr/programming/325933/determine-whether-two-date-ranges-overlap