Số phòng họp tối thiểu

General
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Cho $N$ cuộc họp, cuộc họp thứ $i$ bắt đầu tại $S_i$ và kết thúc tại $E_i$ ($S_i < E_i$). Nếu một cuộc họp kết thúc tại thời điểm $t$ thì cuộc họp khác bắt đầu tại thời điểm $t$ có thể sử dụng chung phòng. Hãy tìm số phòng họp tối thiểu cần thiết để tổ chức hết tất cả $N$ cuộc họp.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên dương $N$.\n$N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $S_i, E_i$.

Dữ liệu ra

Một số nguyên duy nhất là số phòng họp tối thiểu.

Ví dụ
Input Output
3\n0 30\n5 10\n15 20 2
2\n1 5\n5 10 1
Giới hạn

$1 \le N \le 1000$, $0 \le S_i < E_i \le 10^9$.

Draft saved