Chương trình tìm tổng thời lượng duy nhất từ ​​danh sách các khoảng thời gian trong Python

Giả sử chúng ta có một danh sách các khoảng trong đó mỗi danh sách đại diện cho một khoảng [bắt đầu, kết thúc] (bao gồm). Chúng tôi phải tìm tổng thời lượng duy nhất mà nó bao gồm.

Vì vậy, nếu đầu vào giống như khoảng =[[2, 11], [13, 31], [41, 61]], thì đầu ra sẽ là 50, vì tổng khoảng cách được bao phủ duy nhất là (11 - 2 + 1) =10 thì (31 - 13 + 1) =19 và (61 - 41 + 1) =21, do đó tổng là 50.

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

• nếu danh sách khoảng thời gian trống, thì
  • trả về 0
• sắp xếp các khoảng thời gian trong danh sách
• [bắt đầu, kết thúc]:=khoảng [0]
• ans:=0
• đối với mỗi (s, e) bắt đầu và kết thúc trong các khoảng thời gian, hãy thực hiện
  • if s> end, then
    • ans:=ans + end - start + 1
    • start:=s, end:=e
  • nếu không,
    • end:=tối đa của kết thúc, e
• ans:=ans + end - start + 1
• trả lại ans

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):
      if not intervals:
         return 0
         intervals.sort()
         start, end = intervals[0]
         ans = 0
         for s, e in intervals:
            if s > end:
               ans += end - start + 1
               start = s
               end = e
            else:
               end = max(end, e)
            ans += end - start + 1
         return ans
ob = Solution()
intervals = [[2, 11],[13, 31],[41, 61]]
print(ob.solve(intervals))

Đầu vào

[[2, 11],[13, 31],[41, 61]]

Đầu ra

50