(3,5 ĐIỂM) CÁC ĐOẠN TRÊN TRỤC SỐ LINES.PASHAI ĐOẠN [A, B] VÀ [C, D] Đ...

Câu 3: (3,5 điểm) Các đoạn trên trục số LINES.PASHai đoạn [a, b] và [c, d] được gọi là hai đoạn gối nhau nếu xếp chúng trên cùngmột trục số thì điểm đầu của đoạn này trùng với điểm cuối của đoạn kia, tức là c = bhoặc a = d (a < b và c < d). Cho N đoạn trên cùng một trục số được đánh chỉ số từ 1 đến N. Đoạn thứ i cóđiểm đầu a

i

và điểm cuối b

i

(1 ≤ N ≤ 1000, 1 ≤ i ≤ N, -32000 ≤ a

i

, b

i

≤ 32000). Yêu cầu: Hãy tìm các đoạn gối nhau liên tiếp trên trục số sao cho số lượng đoạn gốinhau là lớn nhất.Dữ liệu vào: Ghi trong file văn bản LINES.INP có cấu trúc như sau:- Dòng 1: Ghi số nguyên dương N.- Dòng thứ i trong N dòng tiếp theo: Ghi hai số nguyên a

i

và b

i

tương ứng là điểm đầuvà điểm cuối của đoạn thứ i, hai số được ghi cách nhau ít nhất một dấu cách.Dữ liệu ra: Ghi ra file văn bản LINES.OUT theo cấu trúc như sau:- Dòng 1: Ghi số nguyên K là số lượng đoạn gối nhau tìm được.- Dòng 2: Ghi K số nguyên lần lượt là chỉ số ban đầu của các đoạn gối nhau theo thứtự từ trái sang phải trên trục số, các số được ghi cách nhau một dấu cách.

Ví dụ:

LINES.INP LINES.OUT354 2 52 73 47 91 34 5(Có 55% số test với N ≤ 100; 45% số test với N >100).... Hết ...