Chương trình tìm độ dài của khoảng dài nhất từ ​​danh sách các khoảng trong Python

Giả sử chúng ta có một danh sách các khoảng mà mỗi khoảng có dạng [bắt đầu, kết thúc]. Chúng ta phải tìm ra khoảng thời gian dài nhất mà chúng ta có thể tạo ra bằng cách hợp nhất bất kỳ khoảng thời gian chồng chéo nào.

Vì vậy, nếu đầu vào giống như [[1, 6], [4, 9], [5, 6], [11, 14], [16, 20]], thì đầu ra sẽ là 9, như sau khi hợp nhất, chúng ta có khoảng [1, 9] dài 9.

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

• sắp xếp các khoảng thời gian trong danh sách
• union:=khoảng thời gian đầu tiên từ danh sách các khoảng thời gian
• tốt nhất:=union [end] - union [start] + 1
• đối với mỗi khoảng thời gian bắt đầu s và thời gian kết thúc e trong các khoảng thời gian trừ thời gian đầu tiên, hãy thực hiện
  • nếu s <=union [end] thì
    • union [end]:=tối đa của union [end] và e
  • nếu không,
    • union:=một khoảng thời gian mới [s, e]
  • tốt nhất:=tối đa trong tổng số tốt nhất và union [end] - union [start] + 1
• trở lại tốt nhất

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

Đầu vào

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

Đầu ra

9