Chương trình đếm số khoảng được chứa hoàn toàn bên trong các khoảng khác trong Python

Giả sử chúng ta có một danh sách các khoảng. Trong khoảng danh sách này [i] có các giá trị [bắt đầu, kết thúc]. Chúng ta phải tìm số khoảng được chứa bởi một khoảng khác. Nếu có một khoảng được chứa bởi nhiều khoảng khác mà chỉ nên đếm một lần. Một khoảng [s0, e0] nằm trong một khoảng khác [s1, e1] khi s0 ≤ s1 và e0 ≥ e1.

Vì vậy, nếu đầu vào giống như khoảng =[[2, 6], [3, 4], [4, 7], [5, 5]], thì đầu ra sẽ là 2, bởi vì [3, 4] và [ 5, 5] lần lượt ở bên trong [2, 6] và [4, 7].

Để 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 danh sách khoảng thời gian dựa trên thời gian bắt đầu, khi thời gian bắt đầu giống nhau, hãy sắp xếp theo thứ tự giảm dần của thời gian kết thúc
• end_mx:=-infinity
• ans:=0
• đối với mỗi cặp (bắt đầu, kết thúc) trong các khoảng thời gian, hãy thực hiện
  • nếu kết thúc <=end_mx, thì
    • ans:=ans + 1
  • end_mx:=tối đa end_mx và kết thúc
• trả lại ans

Ví dụ

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

def solve(intervals):
   if not intervals:
      return 0

   intervals.sort(key=lambda x: (x[0], -x[1]))

   end_mx = float("-inf")
   ans = 0

   for start, end in intervals:
      if end <= end_mx:
         ans += 1

      end_mx = max(end_mx, end)

   return ans

intervals = [[2, 6],[3, 4],[4, 7],[5, 5]]
print(solve(intervals))

Đầu vào

[[2, 6],[3, 4],[4, 7],[5, 5]]

Đầu ra

2