Elearning CodePath – CTP Online Judge

Lịch trình công việc

GRD001

🟢 Easy #General #Greedy #Dynamic Programming

### 📌 Thông tin chung

---
### 📝 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