Phát lì xì
Xem dạng PDFNhân dịp bước sang Tết Nguyên Đán ~2025~, cô giáo có rất nhiều bao lì xì giống nhau và muốn trao cho ~K~ bạn học sinh trong lớp.
Tuy nhiên, để thêm phần hấp dẫn, mỗi bạn đều nhận được một lá thăm chứa cặp số nguyên dương (~x_i, y_i~), tức là mỗi bạn sẽ nhận được đoạn số may mắn từ ~[x_i,y_i]~. Cô giáo sẽ chọn ra những số bất kì, nếu số này thuộc trong đoạn số may mắn của bạn nào thì bạn đó sẽ trúng một bao lì xì may mắn. Để trò chơi may rủi nhưng vẫn có sự công bằng, cô giáo muốn chọn những số sao cho mỗi bạn nếu có trúng lì xì thì chỉ được trúng một lần.
Yêu cầu: Giúp cô giáo xác định số bạn tối đa trúng lì xì thỏa yêu cầu trên.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên ~N, K~ lần lượt là giá trị lớn nhất cô giáo có thể chọn, và số bạn trong lớp (~1 \leq N, K \leq 10^6~).
- ~K~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~x_i, y_i~, là cặp số trên lá thăm của bạn thứ ~i~ (~1 \leq x_i \leq y_i \leq N~).
Kết quả ra
- Một số nguyên duy nhất thể hiện số bạn tối đa trúng lì xì.
Ràng buộc
- Subtask ~1~ (~30 \%~): ~1 \leq N, K \leq 20~.
- Subtask ~2~ (~30 \%~): ~1 \leq N, K \leq 10^3~.
- Subtask ~3~ (~40 \%~): Không có ràng buộc gì thêm.
Ví dụ 1
Dữ liệu vào
3 3
1 3
1 2
3 3
Kết quả ra
2
Giải thích
Một cách lựa chọn là cô giáo chỉ chọn số ~1~ hoặc ~2~:
- Bạn thứ ~1~ và bạn thứ ~2~ sẽ được nhận lì xì.
- Lưu ý: Không được chọn thêm số ~3~ vì bạn thứ ~1~ sẽ nhận lì xì hai lần, không thỏa yêu cầu.
Một cách khác là cô giáo chỉ chọn số ~3~:
- Bạn thứ ~1~ và bạn thứ ~3~ sẽ được nhận lì xì.
Ví dụ 2
Dữ liệu vào
5 5
1 3
2 4
4 5
2 5
1 4
Kết quả ra
4
Giải thích
Một cách lựa chọn là cô giáo chọn các số: ~1, 2~:
- Bạn thứ ~1~ và bạn thứ ~5~ sẽ nhận lì xì tương ứng với số ~1~.
- Bạn thứ ~2~ và bạn thứ ~4~ sẽ nhận lì xì tương ứng với số ~2~.
Một cách khác là cô giáo chọn các số: ~1, 5~:
- Bạn thứ ~1~ và bạn thứ ~5~ sẽ nhận lì xì tương ứng với số ~1~.
- Bạn thứ ~3~ và bạn thứ ~4~ sẽ nhận lì xì tương ứng với số ~5~.
Bình luận
.
cách tránh TLE 8 test cuối nha >>