Lập lịch thuê phòng hội nghị
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Một trung tâm hội nghị nhận được $N$ đơn đặt phòng, đơn thứ $i$ biểu diễn bằng struct Booking { long long start, end, profit; }. Hai đơn không xung đột nếu thời điểm kết thúc của đơn trước $\le$ thời điểm bắt đầu của đơn sau. Hãy chọn một tập hợp các đơn không xung đột sao cho tổng lợi nhuận thu được là lớn nhất.
Dữ liệu vào
Dòng đầu chứa số nguyên $N$.
$N$ dòng tiếp theo, mỗi dòng gồm 3 số nguyên start end profit.
Dữ liệu 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 50 2 5 20 4 6 70 6 7 30 |
150 |
| 3 1 4 10 2 3 15 3 5 10 |
25 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le start < end \le 10^9$, $1 \le profit \le 10^9$
Community Discussion