Python에서 간격 목록에 삽입할 수 있는 최소 하나의 간격을 찾는 프로그램

각 행이 [시작, 끝](포함) 간격을 나타내는 간격이라고 하는 2D 숫자 목록이 있다고 가정합니다. 구간 [a, b](a

따라서 입력이 간격 =[[15, 20],[30, 50]]과 같으면 가능한 가장 작은 간격인 간격 [20, 30]을 추가할 수 있으므로 출력은 10이 됩니다.

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

• 이벤트 :=새 목록
• 각 시작 및 종료 시간 s, e 간격으로 수행
  • 이벤트 끝에 (s, 1) 삽입
  • 이벤트 끝에 (e, -1) 삽입
• 목록 이벤트 정렬
• curr_status :=0, 마지막 :=null
• 간격 :=쌍 [0, 0]
• 이벤트의 각 쌍(시간, 상태)에 대해 다음을 수행합니다.
  • curr_status가 0이고 last 및 time> last와 같으면
    • 간격[0]이 0과 같으면
      • 간격[0] :=마지막
    • 간격[1] :=시간
  • 마지막 :=시간
  • curr_status :=curr_status + 상태
• 반환 간격[1] - 간격[0]

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

예

class Solution:
   def solve(self, intervals):
      events = []
      for s, e in intervals:
         events.append((s, 1))
         events.append((e, -1))
      events.sort()
      curr_status = 0
      last = None
      interval = [0, 0]
      for time, status in events:
         if curr_status == 0 and last and time > last:
            if interval[0] == 0:
               interval[0] = last
            interval[1] = time
         last = time
         curr_status += status
      return interval[1] - interval[0]
ob = Solution()
intervals = [[15, 20],[30, 50]] print(ob.solve(intervals))

입력

[[15, 20],[30, 50]]

출력

10