2593. 星港订单
1000ms
512MB
简单
题目描述
星际货运公司收到了 `n` 个订单。第 `i` 个订单有开始时间 `$l_i$`、结束时间 `$r_i$` 和收益 `$p_i$`。
一艘飞船一次只能执行一个订单。若一个订单在时刻 `t` 结束，飞船可以在同一时刻 `t` 开始另一个订单。也就是说，若订单 `i` 满足 $r_i <= l_j$，则这两个订单可以按顺序执行。
请你帮助飞船选择若干个互不冲突的订单，使得总收益最大。
输入格式
第一行一个整数 `n`。
接下来 `n` 行，每行三个整数 `$l_i, r_i, p_i$`。
输出格式
输出一个整数，表示最大总收益。
样例 1
输入 (Input)
输出 (Output)
样例 2
输入 (Input)
输出 (Output)
样例说明
选择第 1 个订单 `[1,3]` 和第 3 个订单 `[4,6]`，总收益为 `10 + 15 = 25`。
虽然第 2 个订单收益为 20，但它与第 1、第 3 个订单都冲突。
- $1 <= n <= 2 \times 10^5$
- $1 <= l_i < r_i <= 10^9$
- $1 <= p_i <= 10^9$
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功