Python의 간격 목록에서 가장 긴 간격의 길이를 찾는 프로그램

<시간/>

각 간격이 [시작, 끝] 형식인 간격 목록이 있다고 가정합니다. 겹치는 간격을 몇 개라도 병합하여 만들 수 있는 가장 긴 간격을 찾아야 합니다.

따라서 입력이 [[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]]과 같으면 병합 후와 같이 출력은 9가 됩니다. 길이가 9인 간격 [1, 9]이 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

목록 간격 정렬
union :=간격 목록의 첫 번째 간격
최고:=합집합[종료] - 합집합[시작] + 1
첫 번째 시간을 제외한 간격의 각 시작 시간 s 및 종료 시간 e에 대해 다음을 수행합니다.
- s <=합집합[end]이면
  - union[end] :=합집합[end] 및 e의 최대값
- 그렇지 않으면
  - union :=새 간격 [s, e]
- best :=best와 union[end]의 최대값 - union[start] + 1
최고의 수익

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def solve(self, intervals):
      intervals.sort()
      union = intervals[0]
      best = union[1] - union[0] + 1
      for s, e in intervals[1:]:
         if s <= union[1]:
            union[1] = max(union[1], e)
         else:
            union = [s, e]
            best = max(best, union[1] - union[0] + 1)
      return best
ob = Solution()
intervals = [[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]]
print(ob.solve(intervals))

입력

[[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]]