Số phòng họp tối thiểu
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề 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$.
Community Discussion