Elearning CodePath – CTP Online Judge

Các Tour Du Lịch

TOURS

🟢 Easy #General #Greedy #Interval #Scheduling

### 📌 Thông tin chung

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

Có $N$ nhóm khách du lịch và $M$ tour du lịch.
* Nhóm thứ $i$ có $P_i$ người.
* Tour du lịch thứ $j$ có hai hạn chế: số người tối thiểu $L_j$ và số người tối đa $R_j$.

Quy tắc:
1.  Mỗi nhóm sẽ chọn **một** tour du lịch.
2.  Mỗi tour du lịch sẽ phục vụ tối đa **một** nhóm.
3.  Một nhóm $i$ có thể đặt tour $j$ nếu $L_j \le P_i \le R_j$.

Yêu cầu:
1.  Tìm số lượng tối đa các tour du lịch có thể tổ chức được (tức là số lượng cặp nhóm-tour thỏa mãn).
2.  Chỉ ra một phương án ghép cặp bất kỳ để đạt số lượng tối đa đó.

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

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

* Dòng đầu tiên: Ghi hai số nguyên dương $N$ và $M$, lần lượt là số nhóm và số tour du lịch. Các nhóm được đánh số từ $1$ đến $N$, các tour từ $1$ đến $M$.
* $N$ dòng tiếp theo: Dòng thứ $i$ chứa số nguyên $P_i$ là số lượng người trong nhóm thứ $i$.
    * $1 \le P_i \le 10^9$.
* $M$ dòng cuối cùng: Dòng thứ $j$ mô tả tour du lịch thứ $j$ gồm hai số nguyên $L_j$ và $R_j$ lần lượt là số lượng người tối thiểu và tối đa của nhóm có thể đặt tour này.
    * $1 \le L_j \le R_j \le 10^9$.

Giới hạn (Không được cho rõ, giả định theo mức độ phức tạp phổ biến):
* $1 \le N, M \le 10^5$.

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

Ghi ra file `TOURS.OUT`:

* Dòng đầu tiên: Ghi số nguyên $K$ - số lượng tour du lịch tối đa có thể tổ chức.
* $K$ dòng tiếp theo: Mỗi dòng mô tả một tour du lịch được lựa chọn gồm 2 số nguyên: số hiệu của nhóm và số hiệu tour du lịch mà nhóm đặt.

---
### ✨ Ví dụ

| Input (`TOURS.INP`) | Output (`TOURS.OUT`) |
| :--- | :--- |
| `5 4` `54` `6` `9` `42` `15` `6 6` `20 50` `2 8` `7 20` | `3` `2 1` `3 4` `4 2` |

---
### 🏷 Phân Subtask

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

---

✅ Đã AC: 0 / 0 submissions