Elearning CodePath – CTP Online Judge

Hạ cánh an toàn

LANDING

🟢 Easy #Greedy #Binary Search #Priority Queue

### 📌 Thông tin chung

### Bài toán

Tại sân bay Cát Bi, có $N$ máy bay đang tiếp cận để hạ cánh tại thời điểm $0$. 
* Máy bay thứ $i$ có thể hạ cánh tại một mốc thời điểm nguyên trong đoạn $[L_i, R_i]$.
* Sân bay có $K$ đường băng hoạt động độc lập.
* Quy tắc giãn cách: Hai máy bay liên tiếp hạ cánh trên cùng một đường băng phải cách nhau ít nhất $X$ giây.

Yêu cầu: 
1. Tìm số lượng máy bay $P$ lớn nhất có thể hạ cánh.
2. Trong các phương án đạt được $P$ máy bay, tìm giá trị $T$ lớn nhất sao cho $T$ là khoảng cách nhỏ nhất giữa hai máy bay bất kỳ trên cùng một đường băng. Nếu mỗi đường băng chỉ có tối đa 1 máy bay, quy ước $T = -1$.

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

Dữ liệu vào từ file LANDING.INP:
* Dòng 1: Ba số nguyên dương $N, K, X$ ($N \le 10^5, K \le 4, X \le 10^9$).
* $N$ dòng tiếp theo: Mỗi dòng ghi hai số nguyên $L_i, R_i$ ($0 \le L_i \le R_i \le 10^9$).

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

Ghi ra file LANDING.OUT một dòng duy nhất chứa hai số nguyên $P$ và $T$.

### ✨ Ví dụ

| LANDING.INP | LANDING.OUT | Giải thích |
| :--- | :--- | :--- |
| 5 1 60 0 20 0 20 100 120 60 80 110 130 | 3 65 | ĐB 1: MB1(0), MB4(65), MB5(130). Khoảng cách: 65, 65. T = 65. |

### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 & 2 | $N \le 8, K \le 2$ | 28% |
| 3 & 4 | $N \le 16, K \le 2, L_i, R_i \le 100$ | 36% |
| 5 | $N \le 10^5, K = 1$ | 20% |
| 6 | $N \le 10^5, 2 \le K \le 4$ | 16% |

✅ Đã AC: 1 / 7 submissions