Chọn Ca Tham Dự · canuc80k0409 · Thuật toán Canuc80k

Có $n$ hoạt động, hoạt động thứ $i$ bắt đầu tại thời điểm $a_{i}$ và kết thúc tại thời điểm $b_{i}$ . Bạn chỉ có thể tham dự một hoạt động tại một thời điểm và phải tham dự trọn vẹn hoạt động đã chọn.

Bạn được phép bắt đầu một hoạt động đúng lúc hoạt động trước kết thúc. Hãy tìm số hoạt động lớn nhất có thể tham dự đầy đủ.

Input

Dòng đầu tiên chứa số nguyên $n$ .
Mỗi dòng trong $n$ dòng tiếp theo chứa hai số nguyên $a_{i}$ và $b_{i}$ , là thời điểm bắt đầu và kết thúc của một hoạt động.

Output

In ra số hoạt động lớn nhất có thể chọn.

Constraints

$1 \leq n \leq 2 \cdot 1 0^{5}$ .
$1 \leq a_{i} < b_{i} \leq 1 0^{9}$ .

Scoring

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

Example

Test 1

Input

Output

Giải thích: Có thể chọn các hoạt động $[1, 4], [5, 6]$ và $[7, 8]$ . Không thể chọn bốn hoạt động vì mọi hoạt động còn lại đều giao thời gian với ít nhất một hoạt động trong lịch này hoặc buộc bỏ một trong ba khoảng đã chọn.

Phân tích: Trong các hoạt động có thể chọn tiếp theo, hoạt động kết thúc sớm nhất chừa lại nhiều thời gian nhất cho phần còn lại. Đây là lựa chọn trội so với một hoạt động đầu tiên kết thúc muộn hơn.
Thuật toán: Sắp xếp hoạt động theo thời điểm kết thúc tăng dần. Duyệt theo thứ tự đó; chọn một hoạt động nếu thời điểm bắt đầu của nó không nhỏ hơn thời điểm kết thúc của hoạt động cuối đã chọn.
Chứng minh: Xét một lịch tối ưu và hoạt động đầu tiên F của lịch. Gọi G là hoạt động kết thúc sớm nhất trong toàn bộ tập hiện còn xét. Vì G kết thúc không muộn hơn F, thay F bằng G vẫn giữ mọi hoạt động sau hợp lệ và không giảm số lượng. Vậy có một lịch tối ưu bắt đầu bằng lựa chọn của thuật toán; lặp lại trên phần thời gian còn lại chứng minh toàn bộ lịch là tối ưu.
Độ phức tạp: Thời gian O(n log n), bộ nhớ O(n).