Có n hoạt động, hoạt động thứ i bắt đầu lúc si và kết thúc lúc fi (một hoạt động chiếm khoảng thời gian [si,fi)). Một người chỉ làm được một hoạt động tại một thời điểm; hai hoạt động i,j không chồng nhau nếu fi≤sj hoặc fj≤si.
Hãy chọn số lượng hoạt động nhiều nhất sao cho không có hai hoạt động nào chồng nhau, rồi in ra số đó.
Đây là bài toán kinh điển giải bằng tham lam: sắp xếp theo thời điểm kết thúc tăng dần, rồi lần lượt chọn hoạt động kết thúc sớm nhất mà không xung đột với hoạt động đã chọn.
Dòng đầu chứa số nguyên n. Tiếp theo là n dòng, mỗi dòng chứa hai số nguyên si fi với si<fi.
1≤n≤105, 0≤si<fi≤109.
In ra một số nguyên là số hoạt động nhiều nhất có thể chọn.
Ví dụ:
Đầu vào:
3
1 3
2 4
3 5
Đầu ra:
2
Giải thích:
Đang tải editor...