Giả sử chúng ta có một danh sách các khoảng thời gian chiếu các bộ phim khác nhau (chúng có thể trùng nhau), chúng ta phải tìm số lượng rạp tối thiểu cần thiết để có thể chiếu tất cả các bộ phim.
Vì vậy, nếu đầu vào giống như khoảng =[[20, 65], [0, 40], [50, 140]], thì đầu ra sẽ là 2, vì [20, 65] và [0, 40] trùng nhau . [20, 65] và [50, 140] cũng trùng nhau nhưng [0, 40] và [50, 140] thì không. Vì vậy, chúng tôi cần 2 rạp chiếu phim.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
- t:=một danh sách mới
- đối với mỗi khoảng [a, b] trong khoảng thời gian, hãy thực hiện
- chèn [a, 1] vào cuối t
- chèn [b, -1] vào cuối t
- ans:=0, count:=0
- đối với mỗi cặp (x, d) trong t ở dạng đã sắp xếp, thực hiện
- count:=count + d
- ans:=tối đa ans và đếm
- trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:
Mã mẫu
class Solution: def solve(self, intervals): t = [] for a, b in intervals: t.append((a, 1)) t.append((b, -1)) ans = count = 0 for x, d in sorted(t): count += d ans = max(ans, count) return ans ob = Solution() intervals = [[20, 65],[0, 40],[50, 140]] print(ob.solve(intervals))
Đầu vào
[[20, 65],[0, 40],[50, 140]]
Đầu ra
2