Tasks and Deadlines

题目描述

你需要处理 $n$ 个任务。每个任务都有一个持续时间和一个截止时间，你将按某个顺序一个接一个地处理这些任务。你对一个任务的奖励是 $d-f$，其中 $d$ 是它的截止时间，$f$ 是你的完成时间。（起始时间为 0，即使某个任务会产生负奖励，你也必须处理所有任务。） 如果你最优地行事，最大的总奖励是多少？

输入格式

第一行输入是一个整数 $n$：任务的数量。 接下来有 $n$ 行描述这些任务。每行有两个整数 $a$ 和 $d$：任务的持续时间和截止时间。

输出格式

输出一个整数：最大的总奖励。

3
6 10
8 15
5 12

2

提示

$1 \le n \le 2 \cdot 10^5$ $1 \le a,d \le 10^6$

标签: CSES1630|排序和搜索

来源

CSES1630|排序和搜索