Lịch Diễn Sân Khấu Nhiều Phòng

Buổi 52 — Mock Contest Phase 2 greedy sorting
Points
20
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Ban tổ chức một liên hoan nghệ thuật quản lý $K$ sân khấu giống hệt nhau và nhận được $N$ đơn đăng ký tiết mục biểu diễn. Tiết mục thứ $i$ diễn ra trong khoảng thời gian nửa mở $[l_i, r_i)$, bắt đầu tại thời điểm $l_i$ và kết thúc tại thời điểm $r_i$ ($l_i < r_i$). Tại bất kỳ thời điểm nào, mỗi sân khấu chỉ phục vụ được tối đa một tiết mục. Nếu tiết mục $i$ kết thúc không muộn hơn lúc tiết mục $j$ bắt đầu ($r_i \le l_j$), cả hai có thể được bố trí lần lượt trên cùng một sân khấu.

Hãy xác định số lượng tiết mục nhiều nhất có thể xếp lịch biểu diễn trên $K$ sân khấu hiện có.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $K$ ($1 \le N \le 10^5$, $1 \le K \le 10^5$).
  • Trong $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $l_i, r_i$ ($1 \le l_i < r_i \le 10^9$).
Dữ liệu ra

In ra một số nguyên duy nhất là số tiết mục tối đa có thể phục vụ.

Ví dụ
Input Output
5 2
1 5
2 4
4 7
5 8
6 9
4
Giới hạn

Thời gian: 1.0s, Bộ nhớ: 256MB.

Draft saved