Elearning CodePath – CTP Online Judge

PHỦ ĐOẠN

PHUDOAN

## Đề bài

Cho đoạn thẳng $[0, M]$ trên trục số và $n$ đoạn thẳng nhỏ $[L_i, R_i]$.

Hãy tìm số lượng đoạn thẳng nhỏ ít nhất cần chọn để phủ kín toàn bộ đoạn $[0, M]$.

Một tập các đoạn được gọi là phủ kín đoạn $[0, M]$ nếu với mọi điểm $x \in [0, M]$, tồn tại ít nhất một đoạn đã chọn chứa điểm $x$.

Nếu không thể phủ kín toàn bộ đoạn $[0, M]$ thì in ra $-1$.

## Dữ liệu vào

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

| Dòng | Nội dung |
|---|---|
| Dòng 1 | Chứa hai số nguyên dương $n, M$ |
| $n$ dòng tiếp theo | Dòng thứ $i$ chứa hai số nguyên $L_i, R_i$ mô tả đoạn thẳng nhỏ thứ $i$ |

## Dữ liệu ra

Ghi ra file `PHUDOAN.OUT` một số nguyên duy nhất là số lượng đoạn thẳng nhỏ ít nhất cần chọn để phủ kín toàn bộ đoạn $[0, M]$. Nếu không thể phủ kín thì ghi ra `-1`.

## Giới hạn

| Thành phần | Ràng buộc |
|---|---|
| $1 \le n \le 2 \times 10^5$ |
| $1 \le M \le 10^9$ |
| $0 \le L_i \le R_i \le 10^9$ |

## Subtask

| Subtask | Điều kiện | Điểm |
|---|---|---|
| 1 | $n \le 20$ | 20\% |
| 2 | $n \le 2000$ | 30\% |
| 3 | Không có ràng buộc gì thêm | 50\% |

## Ví dụ

### Input
4 10
0 3
2 6
4 10
7 10

### Output
3

✅ Đã AC: 3 / 4 submissions