Chương trình tìm một khoảng thời gian tối thiểu có thể để chèn vào danh sách khoảng thời gian trong Python

Giả sử chúng ta có một danh sách 2D các số được gọi là khoảng trong đó mỗi hàng biểu thị khoảng [bắt đầu, kết thúc] (bao gồm). Đối với khoảng [a, b] (a

Vì vậy, nếu đầu vào giống như khoảng =[[15, 20], [30, 50]], thì đầu ra sẽ là 10, vì chúng ta có thể thêm khoảng [20, 30] là khoảng nhỏ nhất có thể.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sự kiện:=một danh sách mới
• đối với mỗi thời gian bắt đầu và kết thúc s, e trong các khoảng thời gian, hãy thực hiện
  • chèn (s, 1) vào cuối sự kiện
  • chèn (e, -1) vào cuối sự kiện
• sắp xếp các sự kiện trong danh sách
• curr_status:=0, last:=null
• khoảng thời gian:=một cặp [0, 0]
• đối với mỗi cặp (thời gian, trạng thái) trong các sự kiện, hãy thực hiện
  • nếu curr_status giống 0 và cuối cùng và thời gian> cuối cùng, thì
    • nếu khoảng [0] giống 0, thì
      • khoảng thời gian [0]:=cuối cùng
    • khoảng thời gian [1]:=thời gian
  • cuối cùng:=time
  • curr_status:=curr_status + trạng thái
• khoảng thời gian trả về [1] - khoảng thời gian [0]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

10