Xếp hộp lồng nhau
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Có $N$ chiếc hộp chữ nhật 2D, chiếc hộp thứ $i$ có kích thước $(w_i, h_i)$ (không được xoay). Chiếc hộp $i$ có thể đặt lọt vào bên trong chiếc hộp $j$ nếu và chỉ nếu $w_i < w_j$ và $h_i < h_j$.
Hãy tìm số lượng hộp nhiều nhất có thể xếp lồng vào nhau thành một chuỗi.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 10^5$).
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $w_i, h_i$ ($1 \le w_i, h_i \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là số hộp tối đa có thể xếp lồng vào nhau.
Ví dụ
| Input | Output |
|---|---|
| 4 5 4 6 4 6 7 2 3 |
3 |
Giới hạn
- $1 \le N \le 10^5, 1 \le w_i, h_i \le 10^9$
Community Discussion