💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
PHỦ ĐOẠN
PHUDOAN
## Đề bài Cho đoạn thẳng $[0, M]$ trên trục số và $n$ đoạn thẳng nhỏ $[L_i, R_i]$. Hãy tìm số lượng đoạn thẳng nhỏ ít nhất cần chọn để phủ kín toàn bộ đoạn $[0, M]$. Một tập các đoạn được gọi là phủ kín đoạn $[0, M]$ nếu với mọi điểm $x \in [0, M]$, tồn tại ít nhất một đoạn đã chọn chứa điểm $x$. Nếu không thể phủ kín toàn bộ đoạn $[0, M]$ thì in ra $-1$. ## Dữ liệu vào Dữ liệu vào từ file `PHUDOAN.INP`. | Dòng | Nội dung | |---|---| | Dòng 1 | Chứa hai số nguyên dương $n, M$ | | $n$ dòng tiếp theo | Dòng thứ $i$ chứa hai số nguyên $L_i, R_i$ mô tả đoạn thẳng nhỏ thứ $i$ | ## Dữ liệu ra Ghi ra file `PHUDOAN.OUT` một số nguyên duy nhất là số lượng đoạn thẳng nhỏ ít nhất cần chọn để phủ kín toàn bộ đoạn $[0, M]$. Nếu không thể phủ kín thì ghi ra `-1`. ## Giới hạn | Thành phần | Ràng buộc | |---|---| | $1 \le n \le 2 \times 10^5$ | | $1 \le M \le 10^9$ | | $0 \le L_i \le R_i \le 10^9$ | ## Subtask | Subtask | Điều kiện | Điểm | |---|---|---| | 1 | $n \le 20$ | 20\% | | 2 | $n \le 2000$ | 30\% | | 3 | Không có ràng buộc gì thêm | 50\% | ## Ví dụ ### Input 4 10 0 3 2 6 4 10 7 10 ### Output 3
✅ Đã AC: 3 / 4 submissions
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng