Làm việc nhóm
Xem dạng PDFTrong công ty XYZ có ~N~ nhân viên xuất sắc. Tuy nhiên, do tất cả đều quá giỏi và quá tự tin, nên nếu có hai nhân viên làm việc tại cùng một thời điểm thì hiệu suất được coi như bằng 0: họ tốn thời gian tranh cãi và không làm được việc gì.
Nhân viên thứ ~i~ có giờ làm việc liên tiếp từ thời điểm ~a_i~ đến ~b_i~ với ~a_i < b_i~.
Do tính chất công việc, mỗi nhân viên không thể thay đổi giờ làm việc của mình.
Do khung thời gian làm việc của các nhân viên không giống nhau hoàn toàn, đôi khi không ai làm việc, đôi khi có một người làm việc, lúc khác lại có nhiều người làm việc nên xảy ra xung đột.
Giám đốc muốn giữ lại một số nhân viên sao cho tổng thời gian làm việc hiệu quả là lớn nhất — nghĩa là không được để hai nhân viên giữ lại có thời gian làm việc giao nhau.
Yêu cầu
Cho ~N~ nhân viên, mỗi nhân viên có khoảng thời gian làm việc ~[a_i, b_i]~.
Hãy chọn ra một tập các nhân viên sao cho:
- Không có hai nhân viên nào có khoảng thời gian làm việc giao nhau.
- Tổng thời gian làm việc:
$$ \sum (b_i - a_i) $$
là lớn nhất.
Dữ liệu
Đọc từ tệp WORKING.INP:
- Dòng 1: số nguyên ~N~ (số nhân viên), ~1 \le N \le 10^5~.
- ~N~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~a_i~ và ~b_i~, biểu diễn thời điểm bắt đầu và kết thúc giờ làm việc của nhân viên thứ ~i~.
Giới hạn:
- ~0 \le a_i < b_i \le 10^9~.
Kết quả
Ghi ra tệp WORKING.OUT:
- Một số nguyên duy nhất là tổng thời gian làm việc hiệu quả lớn nhất có thể đạt được.
Ví dụ
Ví dụ 1
Input
7
100 150
200 300
900 1000
100 1000
900 1800
1900 2000
1800 2000
Output
1800
Chấm điểm
| Subtask | Giới hạn | Mô tả | Điểm |
|---|---|---|---|
| 1 | Khoảng thời gian không giao nhau | Dùng Greedy đơn giản | 20 |
| 2 | ~N \le 10^4~ | Quy hoạch động có sắp xếp | 50 |
| 3 | ~10^4 < N \le 10^5~ | Tối ưu DP nhị phân + nén | 30 |
Bình luận
Do sai sót của thầy KieuTT, Output test là 1250 chứ không phải 1800 🤓👆
Chém