Lập lịch công việc có hạn chót

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

Có $N$ công việc, mỗi công việc mất đúng $1$ đơn vị thời gian để hoàn thành. Công việc thứ $i$ có hạn chót là $d_i$ (phải hoàn thành không muộn hơn thời điểm $d_i$, tức là có thể thực hiện trong khoảng $[t-1, t]$ với $1 \le t \le d_i$) và mang lại lợi nhuận $p_i$. Tại mỗi đơn vị thời gian chỉ có thể làm tối đa một công việc. Hãy chọn và sắp xếp một tập các công việc để đạt tổng lợi nhuận lớn nhất.

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

Một số nguyên duy nhất là tổng lợi nhuận lớn nhất có thể.

Ví dụ
Input Output
4\n4 20\n1 10\n1 40\n1 30 60
5\n2 100\n1 19\n2 27\n1 25\n3 15 142
Giới hạn
  • $1 \le N \le 10^5$
  • $1 \le d_i \le N$
  • $1 \le p_i \le 10^9$
Draft saved