Xếp lịch họp

Buổi 65-66 — Mock HSG greedy sorting
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Có $N$ cuộc họp được đăng ký sử dụng một phòng họp duy nhất. Cuộc họp thứ $i$ bắt đầu vào thời điểm $L_i$ và kết thúc vào thời điểm $R_i$ ($L_i < R_i$). Hai cuộc họp $(L_i, R_i)$ và $(L_j, R_j)$ có thể cùng được chọn nếu $R_i \le L_j$ hoặc $R_j \le L_i$. Hãy chọn ra số lượng cuộc họp nhiều nhất có thể để phục vụ trong phòng họp đó.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$.
  • $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L_i, R_i$.
Dữ liệu ra

In ra số lượng cuộc họp tối đa có thể chọn.

Ví dụ
Input Output
4
1 3
2 5
4 7
6 8
2
3
1 2
2 3
3 4
3
Giới hạn

$1 \le N \le 10^5$, $0 \le L_i < R_i \le 10^9$.

Draft saved