CÁC ĐOẠN NGUYÊN - mã: PBCSEQ - SPOJ

Link: http://vn.spoj.com/problems/PBCSEQ/
==================================

Mirko có một tập hợp các đoạn nguyên. Đầu tiên, anh ấy lấy ra 1 đoạn bất kì. Sau đó thực hiện lấy các đoạn khác, sao cho: đoạn lấy ra nằm trong đoạn vừa được lấy trước nó. Mirko tiếp tục cho đến khi không tìm được đoạn thoả mãn nữa.

Yêu cầu

Tìm số đoạn lớn nhất có thể lấy ra.

Dữ liệu

Dòng đầu tiên chứa số nguyên N, là số đoạn nguyên trong tập hợp.

Dòng thứ i trong số N dòng sau, chứa 2 số nguyên A,B biểu thị cho đoạn i.

Kết quả

Một số duy nhất là kết quả của bài toán.

Giới hạn

1 <= N <= 100000

1 <= A < B <= 1000000

Ví dụ

Dữ liệu

3



1 6



2 5



3 4
 
Kết quả



3

Dữ liệu

6


1 4


1 5

1 6


1 7 


2 5 


3 5
 
Kết quả

5



===========================

Thuật:

- Ta sắp xếp giảm theo A, nếu A bằng thì xếp tăng theo B

- Tìm dãy con không giảm dài nhất trên B => độ dài dãy con không giảm dài nhất chính là kết quả bài toán này

==========================


Code: PBCSEQ.PAS