Lập lịch đơn hàng hạn chót

Buổi 12 — Greedy Algorithm greedy sorting
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Một xưởng gia công nhận được $N$ đơn hàng. Đơn hàng thứ $i$ có hạn chót hoàn thành là $d_i$ và mang lại lợi nhuận là $p_i$. Mỗi đơn hàng mất đúng $1$ đơn vị thời gian để thực hiện (bắt đầu từ thời điểm $0$). Tại mỗi thời điểm chỉ có thể thực hiện tối đa một đơn hàng, và đơn hàng phải hoàn thành không quá hạn chót $d_i$. Hãy tính tổng lợi nhuận lớn nhất có thể thu được.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$.
  • $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $d_i$ và $p_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ụ
Dữ liệu vào Dữ liệu ra
4
2 100
1 19
2 27
1 25
127
Giới hạn
  • $1 \le N \le 10^5$
  • $1 \le d_i \le 10^9$
  • $1 \le p_i \le 10^9$
Draft saved