#1507. QUEUE - Dòng xe vào bến

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

NGUỒN: VOI 2017 - 2018
Test không chính thức (thầy Hồ Đắc Phương)

Bến xe khách liên tỉnh XYZ M điểm đỗ đón xe khách cập bến để hành khách xuống xe. Các điểm đỗ được đánh số từ 1 đến M . Ban điều hành bến xe nhận được yêu cầu cập bến của một dòng xe gồm N xe khách chờ được phục vụ cập bến, lần lượt xe này sau xe kia. Các xe khách được đánh số từ 1 đến N theo thứ tự chờ được phục vụ. Xe khách thứ i chỉ chấp nhận cập bến, nếu như nó được xếp phục vụ tại một trong các điểm đỗ có chỉ số trong khoảng từ a_i đến b_i (1\le a_i \le b_i \le M) và đồng thời tại điểm đỗ được bố trí để phục vụ nó chưa có xe nào trong số các xe (trong dòng xe đang xét) đến trước đã cập bến tại đó. Nếu có một xe khách đến lượt được phục vụ mà Ban điều hành không tìm được điểm đỗ theo đúng yêu cầu để phục vụ nó, thì xe này và tất cả các xe đến sau nó sẽ đồng loạt di chuyển sang bến xe khác và việc phục vụ dòng xe chấm dứt tại đây.

Yêu cầu: Hãy giúp Ban điều hành bến xe xác định số lượng lớn nhất các xe khách trong dòng xe mà bến xe khách XYZ có thể phục vụ đáp ứng các điều kiện đã nêu.

Dữ liệu vào:

  • Dòng đầu tiên chứa số nguyên 𝑇 (1 ≤ 𝑇 ≤ 5) là số lượng test. Tiếp đến là T nhóm dòng, mỗi nhóm là thông tin về một test theo khuôn dạng sau đây:
    • Dòng đầu chứ hai số M, N tương ứng là số lượng điểm đỗ trong bến xe và số lượng xe trong dòng xe yêu cầu được phục vụ;
    • Dòng thứ i trong số N dòng tiếp theo mô tả yêu cầu của xe khách thứ i gồm hai số nguyên a_i b_i (1\le a_i \le b_i \le M) mô tả khoảng chỉ số của các điểm đỗ trong bến xe mà xe khách thứ i chấp nhận được phục vụ tại đó. Hai số trên cùng dọng được ghi cách nhau bởi dấu cách.

Dữ liệu ra:

  • Ghi ra T dòng, mỗi dòng ghi số lượng xe khách lớn nhất trong dòng xe mà bến xe khách XYZ có thể phục vụ là câu trả lời cho test tương ứng trong dữ liệu vào.

Giới hạn:

  • Subtask \#1 (25\%\text{ số điểm}): 1≤ N, M ≤ 10 ;
  • Subtask \#2 (25\% \text{ số điểm}): 1≤ N, M ≤ 300 ;
  • Subtask \#3 (25\% \text{ số điểm}): 1≤ N, M ≤ 50000; a_i=1,i=1,2,\ldots,N ;
  • Subtask \#4 (25\% \text{ số điểm}): 1≤ N, M ≤ 50000 .

Ví dụ:

Dữ liệu vào:
1
4 3
1 4
1 1
1 1
Dữ liệu ra:
2
Dữ liệu vào:
1
4 6
1 2
1 2
1 3
1 3
2 4
1 4
Dữ liệu ra:
3
Giải thích:
  • Trong ví dụ thứ nhất: Xếp xe khách thứ nhất vào một trong các điểm điểm 2, 3, 4 , xếp xe thứ hai vào điểm 1 (duy nhất), xe thứ 3 cũng yêu cầu xếp vào điểm 1 nên không thể đáp úng được.
  • Trong ví dụ thứ hai: Xếp xe thứ 1 và thứ 2 vào hai điểm 1, 2 , xe thứ 3 vào điểm 3 , xe thứ 4 không đáp ứng được nữa.