Lập lịch thuê phòng hội nghị

Binary-search Buổi 07 — Struct & File I/O Buổi 08 — Contest Chặng 1 sorting
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved