Nhân viên cứu hộ (Platinum)

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.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$ nhân viên cứu hộ, mỗi người được phân công một ca trực liên tục được biểu diễn bởi đoạn thời gian $[l_{i}, r_{i}]$ (với $0 \leq l_{i} < r_{i} \leq 10^{9}$ ). Quản lý cần sa thải đúng $K$ nhân viên trong số $N$ nhân viên này.

Hãy tính tổng thời gian bao phủ tối đa có thể đạt được sau khi sa thải đúng $K$ nhân viên. Tổng thời gian bao phủ là độ dài của hợp các đoạn thời gian còn lại.

Dữ liệu vào

Dòng đầu ghi hai số nguyên $N$ và $K$ ( $1 \leq K \leq N \leq 10^{5}$ ).
$N$ dòng tiếp theo, mỗi dòng ghi hai số nguyên $l_{i}$ và $r_{i}$ biểu diễn ca trực của nhân viên thứ $i$ .
Tất cả các giá trị $l_{i}, r_{i}$ đều phân biệt.

Dữ liệu ra

Một số nguyên duy nhất — tổng thời gian bao phủ tối đa sau khi sa thải đúng $K$ nhân viên.

Ràng buộc

$1 \leq K \leq N \leq 10^{5}$
$0 \leq l_{i} < r_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
3 2 1 8 7 15 2 14	12	Sa thải nhân viên $[1, 8]$ và $[2, 14]$ , giữ lại $[7, 15]$ . Tuy nhiên tối ưu là: sa thải $[2, 14]$ và $[7, 15]$ , giữ $[1, 8]$ và... thực ra tối ưu là giữ $[1, 8]$ và $[7, 15]$ : bao phủ $[1, 8] \cup [7, 15]$ = độ dài 12.
5 2 1 5 3 8 7 12 10 15 13 20	16	Giữ lại $[1, 5]$ , $[7, 12]$ , $[13, 20]$ : bao phủ $[1, 5] \cup [7, 12] \cup [13, 20]$ có độ dài $4 + 5 + 7 = 16$ .

Ghi chú

Nếu $K = N$ , tất cả nhân viên đều bị sa thải và tổng bao phủ bằng 0.
Có thể có các đoạn thời gian chồng lấp nhau.

Bình luận

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