Bài 4

Đã đến lễ hội mùa xuân, Bo rất vui vì đã có đủ tiền tham gia lễ hội. Trong lễ hội có rất nhiều trò chơi được tổ chức, Bo muốn sắp xếp thời gian để có thể tham gia nhiều trò chơi nhất có thể mà không trùng về mặt thời gian.

Yêu cầu: Hãy giúp Bo xác định số lượng trò chơi nhiều nhất mà Bo có thể tham gia.

Dữ liệu vào: Số nguyên $N$ ($1 \le N \le 1000$) là số lượng trò chơi, dãy số nguyên $a_i, b_i$ ($1 \le a_i \le b_i \le 10^9$; $i=1..N$) là thời gian bắt đầu và kết thúc của trò chơi thứ $i$.

Kết quả: Là số nguyên xác định số lượng trò chơi nhiều nhất mà Bo có thể tham gia.

• $1 \le N \le 1000$;
• $1 \le a_i \le b_i \le 10^9$.