Nắp Hố Ga Nguyễn Trãi Q5

Mô tả

Mùa mưa đến, tổ sửa chữa công trình đường bộ quận 5 nhận được danh sách N đoạn rãnh nước bị vỡ dọc tuyến đường Nguyễn Trãi. Mỗi đoạn rãnh được ghi nhận bởi tọa độ đầu l[i] và tọa độ cuối r[i] trên trục đường (tính bằng mét, l[i] <= r[i]).

Để khắc phục nhanh chóng, tổ trưởng quyết định dùng một loại nắp hố ga tiêu chuẩn duy nhất có độ dài K để đậy kín tất cả các đoạn rãnh bị vỡ. Nắp hố ga có thể được đặt ở bất kỳ vị trí nào nhưng phải phủ kín hoàn toàn mọi đoạn rãnh: với mỗi đoạn [l[i], r[i]], cần tìm vị trí đặt nắp [start, start + K] sao cho start <= l[i] và start + K >= r[i].

Vì ngân sách hạn hẹp, tổ trưởng muốn bạn tính toán độ dài K nhỏ nhất của nắp hố ga tiêu chuẩn để đậy kín cùng lúc toàn bộ các đoạn rãnh. Nếu chỉ có một đoạn rãnh vỡ, nắp ga chỉ cần vừa khít đoạn đó.

Đầu vào

• Số nguyên N (1 <= N <= 10^5): số lượng đoạn rãnh nước bị vỡ.
• Hai mảng l và r có độ dài N, trong đó l[i] và r[i] là tọa độ đầu và cuối của đoạn rãnh thứ i.

Đầu ra

• Trả về một số nguyên là độ dài nhỏ nhất K của nắp hố ga tiêu chuẩn.

Ràng buộc

• 1 <= N <= 10^5
• 0 <= l[i] <= r[i] <= 10^9
• Tổng số đoạn rãnh có thể chồng lấn lên nhau.

Ví dụ

Ví dụ 1:

• N = 3, l = [1, 4, 2], r = [5, 7, 6]
• Ba đoạn rãnh là [1, 5], [4, 7], [2, 6].
• Nắp hố ga phải đậy được đoạn bắt đầu sớm nhất (vị trí 1) và kết thúc muộn nhất (vị trí 7).
• Độ dài nắp ga nhỏ nhất K = 7 - 1 = 6.
• Đặt nắp tại vị trí [1, 7] phủ kín tất cả ba đoạn rãnh.