题面解释:

在一个基站链式组网中，有 $N$ 个基站，按照从左到右的顺序编号。现有多个“业务”需求，每个业务用三元组表示：起始基站编号、结束基站编号和利润。基站只能被一个业务占用，所选业务集合必须保证没有基站重复使用。目标是选择一组业务，使得总利润最大化。输入包含两个整数 $N$（基站数量，范围 $[1, 10000]$）和 $M$（业务数量，范围 $[1, 100000]$），接下来是 $M$ 行，每行三个整数 $K1$、$K2$ 和 $R$，表示起始基站编号、结束基站编号和利润，其中 $K1, K2 < N$ 且 $K1 < K2$，利润 $R$ 的范围为 $[1, 100]$。输出一个整数，表示能够获得的最大利润。

思路：动态规划

本题为LeetCode原题:1235. 规划兼职工作的化简版

对于处于位置$K2$处的一个可选基站，其占据位置为$[K1,K2]$，利润为$R$。那么如果要选择该基站，上一个基站必须处于$K2$之前。

题目内容

有$N$个基站采用链式组网，按照从左到右编码为$1$到$N$编号。

已知定义“业务”概念为三元组(基站起始编号，基站结束编号，利润)，意味着需要占据基站起始编号到基站结束

编号的所有基站，打通信号流，可以获得对应利润。

现在外部存在多个“业务"需求待接纳，但基站使用具有排他性，也就是说一旦某一个业务占据某个基站，其他

业务不可以再使用此基站。

那么接纳哪些业务需求，可以使得利润最大化?

输入描述

第一行，输入$N$，表示有$N$个基站。$N$取值范围$[1,10000]$

第二行，输入$M$，表示有$M$组业务。,M取值范围$[1,100000]$

接下来$M$行：每行输入三个整数$K1$ $K2$ $R$，以空格隔开，表示起始基站编号，结束基站编号，利润。$K1，K2＜N，K1＜K2$，$R$取值范围$[1,100]$

输出描述

输出只有一个整数，表示获取的利润

样例1

输入

5
2
1 5 4
2 4 8

输出

8

说明

样例2

输入

5
2
1 5 4
2 4 1

输出

4

说明

$1-5$已经使用过，$2$到$4$不能再使用的

样例3

输入

20
6
1 6 1
3 10 2
10 12 3
11 12 2
12 15 2
13 18 1

输出

5

说明

我们可以这么选择业务：

$3$ $10$ $2$；选择$3$到$10$的基站，获利$2$

$11$ $12$ $2$；选择$11$到$12$的基站，获利$2$

$13$ $18$ $1$；选择$13$到$18$的基站，获利$1$

最终获利$5$

也可以选择

$1$ $6$ $1$

$10$ $12$ $3$

$13$ $18$ $1$

注意使用的基站不能重合

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写