Chương trình tìm số rạp chiếu phim tối thiểu để chiếu tất cả các phim trong Python

Mô tả bài toán

Cho danh sách các khoảng thời gian chiếu phim (có thể chồng chéo). Tìm số rạp chiếu tối thiểu để chiếu hết tất cả các suất.

Ví dụ: intervals = [[20, 65], [0, 40], [50, 140]] → đầu ra 2 (suất [20,65] chồng với [0,40] và [50,140], nhưng [0,40] và [50,140] không chồng).

Giải thuật (Sweep Line)

1. Tạo danh sách sự kiện t: với mỗi khoảng [a, b] thêm (a, 1) (bắt đầu) và (b, -1) (kết thúc).
2. Sắp xếp t theo thời gian.
3. Duyệt qua các sự kiện, giữ biến count (số phim đang chiếu) và ans (max của count).
4. Trả về ans.

Ví dụ mã Python

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