Xếp được nhiều cuộc họp nhất

Trung bình

tham lamsắp xếp5 test · 3 giây

Có n cuộc họp, cuộc họp i bắt đầu lúc sᵢ và kết thúc lúc eᵢ. Một phòng họp chỉ chứa được một cuộc họp tại một thời điểm; cuộc họp mới được bắt đầu đúng lúc cuộc trước kết thúc.

Chọn được nhiều cuộc họp nhất là bao nhiêu?

Tham lam: luôn chọn cuộc họp kết thúc sớm nhất còn xếp được.

Dữ liệu vào

Dòng 1: n (1 ≤ n ≤ 2·10⁵).

n dòng: s e (0 ≤ s < e ≤ 10⁹).

Dữ liệu ra

Số cuộc họp tối đa.

Ví dụ

Input

Output

Bài tiếp theo: Số lớn thứ K →

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.