💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
Lịch trình công việc
GRD001
### 📌 Thông tin chung | Mục | Chi tiết | | :--- | :--- | | **Tên File Input** | `TASKS.INP` | | **Tên File Output** | `TASKS.OUT` | --- ### 📝 Bài toán Cho một tập hợp các công việc. Mỗi công việc $i$ được xác định bởi thời gian bắt đầu $S_i$ và thời gian kết thúc $E_i$. Quy tắc: Hai công việc $i$ và $j$ được coi là không thể cùng hoàn thành nếu chúng chồng lấn về thời gian, tức là: $S_i < E_j \quad \text{và} \quad S_j < E_i$ Ngược lại, hai công việc có thể được thực hiện liên tiếp nếu công việc này kết thúc đúng lúc hoặc trước khi công việc kia bắt đầu. Ví dụ, công việc $i$ kết thúc tại $E_i$ và công việc $j$ bắt đầu tại $S_j$: $E_i \le S_j \quad \text{hoặc} \quad E_j \le S_i$ Yêu cầu: Hãy giúp Minh tìm ra được số lượng công việc có thể hoàn thành nhiều nhất (tối đa) mà không có bất kỳ cặp công việc nào chồng lấn nhau. --- ### 📥 Định dạng Đầu vào Dữ liệu vào từ file `TASKS.INP`: * Dòng đầu tiên ghi số nguyên dương $N$ là tổng số công việc. * $N$ dòng tiếp theo, mỗi dòng ghi hai số nguyên $S_i$ và $E_i$ là thời gian bắt đầu và thời gian kết thúc của công việc thứ $i$. Giới hạn: * $1 \le N \le 10^5$. * $0 \le S_i < E_i \le 10^9$. --- ### 📤 Định dạng Đầu ra Ghi ra file `TASKS.OUT` một số nguyên duy nhất là số lượng công việc tối đa có thể hoàn thành. --- ### ✨ Ví dụ | Task | Start (h) | End (h) | | :---: | :---: | :---: | | làm btl môn A | 8 | 10 | | viết bài viblo | 9 | 11 | | ôn tập môn B | 10 | 12 | | nghe nhạc | 14 | 15 | | chạy bộ | 17 | 18 | Tổng số công việc: 5. * **Trường hợp 1:** Chọn `viết bài viblo` (9-11). $\implies$ Không thể chọn 8-10 và 10-12. * Các task còn lại: 14-15, 17-18. $\implies$ Tổng số task: 3 (`viết bài viblo`, `nghe nhạc`, `chạy bộ`). * **Trường hợp 2:** Không chọn `viết bài viblo`. * Có thể chọn: `làm btl môn A` (8-10) $\to$ `ôn tập môn B` (10-12) $\to$ `nghe nhạc` (14-15) $\to$ `chạy bộ` (17-18). * $\implies$ Tổng số task tối đa: **4**. --- ### 🏷 Subtasks | Subtask | Ràng buộc | Tỷ lệ điểm | | :--- | :--- | :--- | | $40\%$ | $N \le 100$; $E_i \le 100$ | $40\%$ | | $30\%$ | $N \le 10^4$; $E_i \le 10^6$ | $30\%$ | | $30\%$ | $N \le 10^5$; $E_i \le 10^9$ | $30\%$ | ---
✅ Đã AC: 4 / 5 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