Chương trình tìm vùng dọc rộng nhất không chứa điểm nào trong Python

Cho n điểm (x, y). Vùng dọc (vertical area) là dải mở rộng vô hạn theo trục y. Tìm khoảng cách ngang lớn nhất giữa 2 điểm liên tiếp (theo x) sao cho không có điểm nào nằm trong dải đó.

Ví dụ: pts = [[10,9],[11,11],[9,6],[11,9]] → 1. Sắp xếp theo x: [9,6], [10,9], [11,11], [11,9]. Khoảng cách max giữa các x liên tiếp = 1.

Giải thuật

1. Sắp xếp pts theo tọa độ x.
2. Duyệt i từ 1 đến len(pts)-1, tính pts[i][0] - pts[i-1][0].
3. Trả về giá trị lớn nhất.

Ví dụ minh họa

def solve(pts):
    pts.sort()
    return max(pts[i][0] - pts[i-1][0] for i in range(1, len(pts)))

print(solve([[10,9],[11,11],[9,6],[11,9]]))

Đầu vào

[[10,9],[11,11],[9,6],[11,9]]

Đầu ra

1