Chọn Đoạn Không Giao
Nộp bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Python 3
5.0s
Giới hạn bộ nhớ:
256M
Đầu vào:
stdin
Đầu ra:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++, Go, Java, Kotlin, Pascal, Python, Scratch
Cho đoạn thẳng song song với các trục tọa độ (ngang hoặc dọc). Không có hai đoạn ngang nào giao nhau, và không có hai đoạn dọc nào giao nhau.
Hãy chọn nhiều đoạn nhất sao cho không có hai đoạn nào giao nhau (kể cả tại điểm mút).
Dữ liệu vào
- Dòng 1: Số nguyên
- dòng tiếp theo: Bốn số nguyên — tọa độ hai đầu mút
Dữ liệu ra
- In ra số đoạn tối đa có thể chọn.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 4 5 10 5 6 2 6 12 8 3 8 5 |
2 | Chọn hai đoạn dọc (không giao nhau) |
| 4 1 1 2 1 2 1 2 6 1 1 1 3 1 3 4 3 |
2 | Chọn tối đa 2 đoạn không giao |
Bình luận