#78. SEGMENT (Mã bài: SEGMENT)

Bạn được cho đoạn thẳng trên trục tọa độ Ox. Đoạn thẳng thứ được ký hiệu () và bao phủ toàn bộ các điểm nguyên thỏa mãn .

Một vị trí nguyên được gọi là tệ nếu như có nhiều hơn đoạn bao phủ điểm nó.

Yêu cầu: Hãy tính số đoạn thẳng ít nhất cần xóa để không còn vị trí tệ nào.

Dữ liệu:

• Dòng đầu tiên gồm hai số nguyên và ().
• dòng tiếp theo, mỗi dòng gồm hai số nguyên và () — hai đầu của đoạn thẳng thứ .

Kết quả: Một số nguyên duy nhất là số đoạn thẳng cần xóa.

Ví dụ: Dữ liệu:

7 2
5 5
3 5
1 2
2 3
1 2
3 5
1 3

Kết quả:

3

Dữ liệu:

3 1
1 2
3 4
5 6

Kết quả:

0

Giải thích: Ở ví dụ đầu tiên, ta có thể chọn xóa các đoạn thẳng 4, 6 và 7.

Giới hạn:

• Subtask #1 (30%): .
• Subtask #2 (30%): .
• Subtask #3 (20%): .
• Subtask #4 (20%): Không có ràng buộc gì thêm.