간격 목록이 있다고 가정합니다. 이 목록에서 간격[i]에는 [시작, 끝] 값이 있습니다. 다른 간격에 포함된 간격의 수를 찾아야 합니다. 한 번만 계산되어야 하는 여러 다른 간격에 포함된 간격이 있는 경우. 구간 [s0, e0]은 s0 ≤ s1 및 e0 ≥ e1일 때 다른 구간 [s1, e1] 안에 있습니다.
따라서 입력이 간격 =[[2, 6],[3, 4],[4, 7],[5, 5]]와 같으면 출력은 [3, 4] 및 [ 5, 5]는 각각 [2, 6]과 [4, 7] 안에 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 간격 목록이 비어 있으면
- 0을 반환
- 시작 시간을 기준으로 간격 목록 정렬, 시작 시간이 같으면 종료 시간의 내림차순으로 정렬
- end_mx :=-무한대
- ans :=0
- 각 (시작, 끝) 쌍에 대해 간격을 두고 수행합니다.
- 끝이 <=end_mx이면
- ans :=ans + 1
- end_mx :=end_mx 및 end의 최대값
- 끝이 <=end_mx이면
- 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: (x[0], -x[1]))
end_mx = float("-inf")
ans = 0
for start, end in intervals:
if end <= end_mx:
ans += 1
end_mx = max(end_mx, end)
return ans
intervals = [[2, 6],[3, 4],[4, 7],[5, 5]]
print(solve(intervals)) 입력
[[2, 6],[3, 4],[4, 7],[5, 5]]
출력
2