Giờ Cao Điểm · canuc80k3900 · Thuật toán Canuc80k

Có $n$ khoảng thời gian nửa mở $[a_{i}, b_{i})$ , biểu diễn thời gian hiện diện của $n$ đối tượng. Hãy tìm số đối tượng lớn nhất cùng hiện diện tại một thời điểm.

Input

Dòng đầu chứa số nguyên $n$ .
Mỗi trong $n$ dòng tiếp theo chứa hai số nguyên $a_{i}$ và $b_{i}$ .

Output

In một số nguyên là số khoảng cùng phủ một thời điểm lớn nhất.

Constraints

$1 \leq n \leq 2 \cdot 1 0^{5}$ .
$1 \leq a_{i} < b_{i} \leq 1 0^{9}$ .
Toàn bộ $2 n$ thời điểm $a_{i}$ và $b_{i}$ đôi một khác nhau.
Khoảng hiện diện là $[a_{i}, b_{i})$ : đối tượng không còn hiện diện tại đúng thời điểm $b_{i}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 10$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Trong khoảng từ thời điểm $3$ đến trước $4$ , ba khoảng $[1, 4), [2, 5)$ và $[3, 7)$ cùng hoạt động; không có thời điểm nào được bốn khoảng phủ.

Ý tưởng: Sắp xếp các sự kiện bắt đầu/kết thúc rồi quét tổng đang hoạt động.
Ý tưởng: 1. Tạo sự kiện (a_i,+1) và (b_i,-1) cho mỗi khách. 2. Sắp xếp cặp (thời điểm, delta). Với cùng thời điểm, -1 tự đứng trước +1. 3. Quét từ trái sang phải, cập nhật cur += delta và lấy ans = max(ans,cur).
Tính đúng đắn: 1. Ngay sau khi xử lý mọi sự kiện tại thời điểm t, cur đúng bằng số khoảng [a_i,b_i) chứa t. 2. Số khách chỉ thay đổi tại một thời điểm đến hoặc rời; trên mọi khoảng giữa hai sự kiện, nó không đổi. 3. Vì ans lấy cực đại sau mọi lần thay đổi, ans bằng cực đại toàn cục.
Độ phức tạp: O(n log n) thời gian và O(n) bộ nhớ.
Lưu ý cài đặt: Nhầm khoảng đóng với nửa mở.
Lưu ý cài đặt: Duyệt từng thời điểm khi tọa độ rất lớn.
Lưu ý cài đặt: Không xác định tie-break tại cùng thời điểm.