Cho N đoạn số nguyên [ai,bi] (ai<bi và |ai|,|bi|<=109), hãy chọn tập S gồm ít số nguyên nhất mà mỗi đoạn trên đều chứa ít nhất hai số trong tập S
Input:
- Dòng 1 chứa số N (N<=105);
- N dòng tiếp, dòng thứ i chứa 2 số ai và bi.
Output:
- Dòng 1 ghi số lượng số trong tập S
- Dòng 2 ghi các số trong tập S từ nhỏ đến lớn, nếu có nhiều tập thỏa mãn thì chọn tập có giá trị các số lớn hơn.
Input
5
0 10
2 3
4 7
3 5
5 8
Output
4
2 3 5 7
Giải thích:
Có 2 tập thỏa mãn là {2; 3; 5; 6} và {2; 3; 5; 7} thì ta chọn tập {2; 3; 5; 7} có giá trị các số trong tập lớn hơn
Nguồn: DBBB14 Bắc Giang