Lịch Trình Không Giao Nhau
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Có $N$ dự án, dự án thứ $i$ diễn ra từ ngày $L_i$ đến ngày $R_i$ (tính cả hai đầu mút) và mang lại lợi nhuận $W_i$.
Bạn có thể chọn thực hiện một tập hợp các dự án sao cho không có hai dự án nào giao nhau về thời gian (tức là nếu chọn dự án $a$ và dự án $b$ với $R_a < R_b$ thì bắt buộc $R_a < L_b$). Hãy tìm tổng lợi nhuận lớn nhất có thể đạt được.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên dương $N$. $N$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $L_i, R_i, W_i$.
Dữ liệu ra
In ra một số nguyên duy nhất là tổng lợi nhuận lớn nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 1 3 5 2 5 6 4 6 5 1 6 8 |
10 |
| 3 1 5 10 5 10 10 6 10 10 |
20 |
Giới hạn
- $1 \le N \le 2 \cdot 10^5$
- $1 \le L_i \le R_i \le 10^9$
- $1 \le W_i \le 10^9$
Community Discussion