Liên Hoan Phim II

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $n$ bộ phim chiếu tại một liên hoan, mỗi bộ phim chiếu từ thời điểm $a$ đến $b$ . Câu lạc bộ điện ảnh có $k$ thành viên, mỗi người chỉ xem được một bộ phim tại một thời điểm và phải xem từ đầu đến cuối. Hãy tính số phim tối đa mà cả nhóm có thể xem.

Dữ liệu vào

Dòng 1: hai số nguyên $n$ và $k$ .
Dòng $2, \dots, n + 1$ : mỗi dòng gồm hai số nguyên $a$ và $b$ ( $a < b$ ) — thời điểm bắt đầu và kết thúc của phim.

Dữ liệu ra

In một số nguyên — số phim tối đa cả nhóm xem được.

Ràng buộc

$1 \leq k \leq n \leq 2 \cdot 10^{5}$
$1 \leq a < b \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
5 2 1 5 8 10 3 6 2 5 6 9	4	Thành viên 1 xem phim 1 (1–5) và phim 2 (8–10). Thành viên 2 xem phim 4 (2–5) và phim 5 (6–9). Tổng 4 phim.
3 1 1 3 2 4 3 5	2	Một người tối đa xem 2 phim không trùng: phim 1 (1–3) và phim 3 (3–5).

Bình luận

Không có bình luận tại thời điểm này.