닫힌 간격 목록이 두 개 있다고 가정합니다. 여기서 각 간격 목록은 쌍으로 분리되고 정렬된 순서입니다. 이 두 구간 목록의 교차점을 찾아야 합니다.
닫힌 구간 [a, b]는 <=b로 표시됩니다. a <=x <=b인 실수 집합 x. 두 개의 닫힌 간격의 교집합은 비어 있거나 닫힌 간격으로 표시될 수 있는 실수 집합입니다.
따라서 입력이 A =[[0,2],[5,10],[13,23],[24,25]] 및 B =[[1,5],[8,12],[ 15,24],[25,27]], 출력은 [[1,2],[5,5],[8,10],[15,23],[24,24],[25 ,25]].
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
목록을 만들고 I :=0 및 j :=0
으로 설정합니다. -
intersect()라는 메서드를 정의합니다. a와 b -
-
a[0] <=b[0] 및 a[1]>=b[0]이면 true를 반환합니다.
-
그렇지 않으면 b[0] <=a[0] 및 b[1]>=a[0]이면 true를 반환하고, 그렇지 않으면 False를 반환합니다.
-
I B의 크기
동안-
교차하는 경우(A[i], B[i])
-
temp :=A[i, 0], B[j, 0]의 최대값, A[i,1] 및 B[j, 1]의 최소값
-
A[i,0] :=온도[1] + 1, B[j,0] :=온도[1] + 1
-
A[i,0]> A[i,1] 또는 A[i,1] <=temp[0]이면 i를 1만큼 증가
-
B[j,0]>B[j,1] 또는 B[j,1] <=temp[0]인 경우:j를 1만큼 증가
-
결과.추가(임시)
-
다음 반복으로 건너뛰기
-
-
A[i,0]> B[j, 1]이면 j를 1만큼 증가시키고, 그렇지 않으면 i를 1만큼 증가시킵니다.
-
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution(object): def intervalIntersection(self, A, B): result = [] i,j = 0,0 while i < len(A) and j < len(B): if self.intersect(A[i],B[j]): temp = [max(A[i][0],B[j][0]),min(A[i][1],B[j][1])] A[i][0]=temp[1]+1 B[j][0] = temp[1]+1 if A[i][0] > A[i][1] or A[i][1] <= temp[0]: i+=1 if B[j][0]>B[j][1] or B[j][1] <= temp[0]: j+=1 result.append(temp) continue if A[i][0]>B[j][1]: j+=1 else: i+=1 return result def intersect(self,a,b): if a[0]<=b[0] and a[1]>=b[0]: return True if b[0]<=a[0] and b[1] >=a[0]: return True return False ob = Solution() print(ob.intervalIntersection([[0,2],[5,10],[13,23],[24,25]],[[1,5],[8,12],[15,24],[25,27]]))
입력
[[0,2],[5,10],[13,23],[24,25]] [[1,5],[8,12],[15,24],[25,27]]
출력
[[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]