파이썬에서 간격을 병합하고 오름차순으로 정렬하는 프로그램

목록 간격이 있다고 가정하고 정렬된 순서로 이들의 합집합을 찾아야 합니다.

따라서 입력이 inv =[[2, 5],[4, 10],[20, 25]]와 같으면 출력은 [[2, 10], [20, 25]]

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

• 목록 간격 정렬
• ans :=새 목록
• 각 시작과 끝(s, e) 간격에 대해 다음을 수행합니다.
  • 만약 ans와 s가 <=ans의 마지막 간격의 종료 시간이면
    • as의 마지막 간격의 종료 시간 :=e의 최대값 및 ans의 마지막 간격의 종료 시간
  • 그렇지 않으면
    • 간격 [s, e]를 ans에 삽입
• 반환

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

예시

class Solution:
   def solve(self, intervals):
      intervals.sort()
      ans = []
      for s, e in intervals:
         if ans and s <= ans[-1][1]:
            ans[-1][1] = max(ans[-1][1], e)
         else:
            ans.append([s, e])
      return ans
ob = Solution()
inv = [[2, 5],[4, 10],[20, 25]]
print(ob.solve(inv))

입력

[[2, 5],[4, 10],[20, 25]]

출력

[[2, 10], [20, 25]]