Elearning CodePath – CTP Online Judge

Classroom Usage Time

GEN017

🟢 Hard #General #Greedy

### 📌 Thông tin chung

---
### 📝 Bài toán

Có $N$ lớp học đăng ký sử dụng phòng học.
Mỗi lớp đăng ký được xác định bởi:
* $l$: Thời gian bắt đầu sử dụng.
* $d$: Thời lượng sử dụng.

Khoảng thời gian sử dụng của lớp $i$ là đoạn $[l_i, l_i + d_i)$.

Yêu cầu: Tính **tổng thời gian thực sự** mà các phòng học được sử dụng, không tính phần thời gian bị trùng lặp giữa các lớp.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `BAI3.INP`:

* Dòng đầu tiên: Số nguyên $N$ – số lớp đăng ký sử dụng phòng.
* $N$ dòng tiếp theo: Mỗi dòng gồm 2 số nguyên $l$ và $d$.

Giới hạn:
* $1 \le N \le 10^5$.
* $0 \le l \le 10^6$.
* $1 \le d \le 10^6$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `BAI3.OUT` gồm một dòng duy nhất là tổng số đơn vị thời gian mà phòng được sử dụng không trùng lặp.

---
### ✨ Ví dụ

| Input (`BAI3.INP`) | Output (`BAI3.OUT`) | Giải thích |
| :--- | :--- | :--- |
| `3` `1 3` `2 4` `10 2` | `7` | Lớp 1: $[1, 1+3) = [1, 4)$. Lớp 2: $[2, 2+4) = [2, 6)$. Lớp 3: $[10, 10+2) = [10, 12)$. Gộp $[1, 4)$ và $[2, 6)$ thành $[1, 6)$. Tổng thời gian: Độ dài $([1, 6)) + $ Độ dài $([10, 12)) = (6 - 1) + (12 - 10) = 5 + 2 = 7$. |

---
### 🏷 Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 5000$ | $40\%$ |
| 2 | $N \le 10^5$ | $60\%$ |

---

✅ Đã AC: 5 / 12 submissions