값 (a,b)로 구성된 간격 세트가 주어졌다고 가정합니다. 여기서 b는 이벤트의 시작 시간을 나타내고 b는 이벤트의 종료 시간을 나타냅니다. 우리의 임무는 이러한 간격 중 하나가 이 세트의 다른 간격과 완전히 겹치는지 확인하는 것입니다. 간격 중 하나라도 겹치면 결과를 True로 반환하고 그렇지 않으면 False를 반환합니다.
따라서 입력이 [(4,6), (10,12), (7,9), (13,16)]과 같으면 출력은 False가 됩니다. 입력이 [(4,6), (4,9), (7,11), (5,8)]과 같으면 출력은 True가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 목록 간격 정렬
- 범위 1에서 간격 크기까지 i에 대해 다음을 수행합니다.
- 간격[i, 1] <=간격[i- 1, 1]이면
- 참 반환
- 거짓을 반환
- 간격[i, 1] <=간격[i- 1, 1]이면
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
def solve(intervals): intervals.sort() for i in range(1, len(intervals)): if intervals[i][1] <= intervals[i- 1][1]: return True return False intervals = [(4,6),(10,12),(7,9),(13,16)] intervals2 = [(4,6), (4,9), (7,11), (5,8)] print(solve(intervals)) print(solve(intervals2))
입력
[(4,6),(10,12),(7,9),(13,16)] [(4,6), (4,9), (7,11), (5,8)]
출력
False True