P2949 [USACO09OPEN] Work Scheduling G

农夫约翰有很多工作要做！为了高效地经营农场，他必须从他所做的每一项工作中赚取利润，每项工作只需要一个时间单位。 他的工作日从时间 0 开始，总共有 1,000,000,000 个时间单位。他目前可以从 N (1 \leq N \leq 100,000) 项工作中选择要做的工作，这些工作被方便地编号为 1 到 N。 虽然理论上他有可能完成所有 N 项工作，但实际上这是极不可能的，因为他在任何一个时间单位内只能完成一项工作，而截止日期通常会导致他无法完成所有任务。 第 $i$ 项工作的截止时间为 $D_i$ (1 \leq D_i \leq 1,000,000,000)。如果他在截止时间前完成第 $i$ 项工作，他将获得 $P_i$ (1 \leq P_i \leq 1,000,000,000) 的利润。 给定一系列工作和截止日期，FJ 能够获得的最大总利润是多少？答案可能无法容纳在 32 位整数中。

无

无

在时间 1 完成工作 3 (1,7)，在时间 2 完成工作 1 (2,10) 以最大化收益 (7 + 10 -> 17)。 （由 ChatGPT 4o 翻译）