题解 样例分析 思路 nnn 个时间段 [li,ri][l_i,r_i][l i ,r i ]，按照开始时间从小到大排序。 定义dp[i]dp[i]dp[i]，表示以第 iii 个线段结尾的摸鱼时间最大值 需要考虑 dpdpdp 的起始状态、状态转移方程、输出的最终结果。 起始状态 可能有 lil_il i 相同的时间段，需要把和 l1l_1l 1 相同的 lil_il i 这个时间段全部赋初值。 状态转移方程 假设 第 iii 个时间段是由第 jjj 个时间段转移来的( i 到 j 之间的时间段为 k )。需要符合的条件： * lil_il i >rjr_jr j * max(lk)max(l_k)max(l k ) ≤\leq≤ rjr_jr j 输出最终结果 考虑哪一个时间段可以作为结尾？ 假设结尾的时间段为 iii， 需要满足的条件为： * ri≥lnr_i \geq l_nr i ≥l n 优化 上述时间复杂度 O(n3)O(n^3)O(n 3 ) 寻找合适的 jjj 线段可以优化： 复杂度 O(n2)O(n^2)O(n 2 )

摸鱼 视频题解点击此处查看 题目阅读 AC狗在家上网课，狗星教育局对于线上课没有经验，导致了AC狗有了摸鱼机会，现在给你AC狗的上课时间 T分钟， 从1分钟到T分钟结束，AC狗只能在每堂课开始进入课堂，并且要完整上完这堂课，如果当前没在上课并且其他课程开始了，那么ac狗就要选择一堂课去上。现在让你帮他计算最多能摸鱼多久？ 题意抽象 给定一个最大值T，和N个区间，区间的范围一定在1~T内，同时如果选择了一个区间进入后就不用选择其他有冲突的区间（指区间发生交叉），问你有没有一种方法可以使区间覆盖的区域最小。 算法分析 本题我们可以采用线性DP + 二分 + 递归的做法来实现。 根据t和n输入数据后，我们通过起点A与时长W分钟推算出下课时间，同时记录下时间为A时开课的数量，以起点A开始的课程数+1，之后进入递归查找最优解。 通过二分函数查找大于等于坐标now的课程下标，如果已经为最后一节课则直接返回dp[now] = t - now + 1 。 取出该课程的起点，遍历以该课程为起点开始的所有的结束课程时间，查找两者之间跨度最大的课程即可。 代码讲解

/* 求空闲时间 不上课的时间 如果可以上课 必须去 错过开课时间 就无法去 14 7 1 3 23 7 24 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 1 2 2 2 2 3 3 3 */