Chương trình Python đếm khoảng thời gian bị bao hoàn toàn bởi khoảng khác

Cho danh sách khoảng intervals, mỗi khoảng [start, end]. Đếm số khoảng bị chứa hoàn toàn bởi ít nhất một khoảng khác. Khoảng [s0, e0] nằm trong [s1, e1] nếu s1 ≤ s0 và e0 ≤ e1. Mỗi khoảng chỉ đếm tối đa 1 lần dù bị bao bởi nhiều khoảng.

Ví dụ

Input: intervals = [[2,6],[3,4],[4,7],[5,5]]

Output: 2

Giải thích: [3,4] nằm trong [2,6]; [5,5] nằm trong [4,7].

Thuật toán (Sắp xếp + Duyệt một lần)

1. Sắp xếp intervals theo start tăng dần, nếu start bằng nhau thì end giảm dần.
2. Duyệt theo thứ tự, giữ end_mx = end lớn nhất đã thấy.
3. Nếu end ≤ end_mx → khoảng hiện tại bị bao bởi khoảng trước đó → đếm++.
4. Cập nhật end_mx = max(end_mx, end).

Mã nguồn Python

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

# Test
intervals = [[2, 6], [3, 4], [4, 7], [5, 5]]
print(solve(intervals))  # Output: 2

Độ phức tạp

• Thời gian: O(n log n) do sắp xếp.
• Không gian: O(1) (không tính không gian sắp xếp).