Elearning CodePath – CTP Online Judge

Xoá bỏ đoạn thừa

XOABODOANTHUA

## Đề bài

Cho $n$ đoạn thẳng $[L_i, R_i]$ trên trục số.

Một đoạn $[L_i, R_i]$ được gọi là thừa nếu tồn tại một đoạn khác $[L_j, R_j]$ với $j \ne i$ sao cho:

$L_j \le L_i \quad \text{và} \quad R_i \le R_j$

Nói cách khác, đoạn thứ $i$ nằm trọn trong đoạn thứ $j$.

Lưu ý:
- Nếu hai đoạn hoàn toàn trùng nhau, thì mỗi đoạn đều được xem là thừa, vì nó nằm trọn trong một đoạn khác.
- Chỉ những đoạn không thừa mới được tính vào kết quả.

Hãy đếm số lượng đoạn không thừa.

## Dữ liệu vào

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

| Dòng | Nội dung |
|---|---|
| Dòng 1 | Chứa số nguyên dương $n$ |
| $n$ dòng tiếp theo | Dòng thứ $i$ chứa hai số nguyên $L_i, R_i$ |

## Dữ liệu ra

Ghi ra file `XOABODOANTHUA.OUT` một số nguyên duy nhất là số lượng đoạn không thừa.

## Giới hạn

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

## Subtask

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

## Ví dụ 1

### Input
5
1 10
2 5
3 4
6 8
11 12

### Output
2

### Giải thích
Các đoạn $[2,5]$, $[3,4]$, $[6,8]$ đều nằm trọn trong đoạn $[1,10]$ nên là các đoạn thừa.
Hai đoạn không thừa là $[1,10]$ và $[11,12]$.

## Ví dụ 2

### Input
4
1 5
1 5
2 4
6 7

### Output
1

### Giải thích

Hai đoạn $[1,5]$ trùng nhau nên mỗi đoạn đều là thừa.

Đoạn $[2,4]$ nằm trọn trong $[1,5]$ nên cũng là thừa.

Chỉ có đoạn $[6,7]$ là không thừa.

✅ Đã AC: 2 / 14 submissions