Python에서 대상 간격을 병합하여 간격을 찾는 프로그램

겹치지 않는 간격 목록이 있다고 가정합니다. 종료 시간을 기준으로 정렬됩니다. 다른 간격 대상이 있습니다. 간격이 여전히 겹치지 않고 정렬되도록 대상을 병합한 후 최종 간격을 찾습니다.

따라서 입력이 간격 =[[1, 15],[25, 35],[75, 90]], 대상 =[10, 30]인 경우 출력은 [[1, 35], [ 75, 90]] 처음 두 간격 [1, 15] 및 [25, 35]가 병합됩니다.

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

• iv의 끝에 대상 삽입

• 시작 시간을 기준으로 iv 정렬

• res :=첫 번째 간격이 있는 새 목록

• 나는 :=1

• 동안 나는

  • iv[i]의 시작 시간 <=res의 마지막 간격의 종료 시간인 경우

    • res의 마지막 간격의 종료 시간 =최대(res의 마지막 간격의 종료 시간 및 iv[i]의 종료 시간)

  • 그렇지 않으면

    • res

      끝에 iv[i] 삽입

  • 나는 :=나는 + 1

• 반환 해상도

예제(파이썬)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

class Solution:
   def solve(self, iv, target):
      iv.append(target)
      iv.sort(key=lambda x: x[0])
      res = [iv[0]]
      i = 1
      while i < len(iv):
         if iv[i][0] <= res[-1][1]:
            res[-1][1] = max(res[-1][1], iv[i][1])
         else:
            res.append(iv[i])
         i += 1
      return res
ob = Solution()
intervals = [
   [1, 15],
   [25, 35],
   [75, 90]
]
target = [10, 30]
print(ob.solve(intervals, target))

입력

[[1, 15],[25, 35],[75, 90]], [10, 30]

출력

[[1, 35], [75, 90]]