这篇总结不太一样,为了纪念和我爸喋喋不休吵了近3h的时间和教训,用Deepseek共同完成 :
题目
T674176 T2-任务task
题目描述
时间限制: 2.0 秒
空间限制: 512 MiB
有 \(n\) 个任务,第 \(i\) 个任务需要占据 \([l_i,r_i]\) 的时间,每个任务都会在瞬间结束,不会干扰到之后的任务。
你需要保证只使用 \(k\) 条并行线路完成任务,具体来说:
在选择任务后,你有 \(k\) 个流水线,第 \(t\) 流水线能分配若干任务 \([l_{t,i},r_{t,i}]\)。
合法方案需要满足 \(l_{t,i+1}\ge r_{t,i}\),即结束时间不能超过下一个开始时间,且所有任务都分配进去。
也就是说:
- 对于区间 \([1,2],[2,3]\),可以分配到一条流水线上;
- 对于全部是 \([1,1]\) 区间的任务,都可以将其安排在一条流水线上;
- 但是如果是 \([2,2]\) 和 \([1,3]\) 两个区间就无法安排在一条流水线上。
输入格式
从标准输入读入数据。
第一行两个正整数 \(n,k\),表示任务的数量和同时最多能做的任务数。
接下来 \(n\) 行,第 \(i+1\) 行两个整数表示 \(l_i,r_i\)。
输出格式
输出到标准输出。
输出一行一个整数,表示最多能完成的任务数。
输入输出样例 #1
输入 #1
3 1
1 2
2 3
1 3
输出 #1
2
说明/提示
补充样例0输入
3 1
1 1
1 1
1 1
样例0输出
3
样例1解释
做任务 \(1\) 和任务 \(2\)。注意任务 \(1\) 结束的那一刻不算正在做任务 \(1\),可以立即开始任务 \(2\)。
对于所有的数据,1 ≤ k ≤n ≤ 10⁶, 0 ≤ lᵢ ≤ rᵢ ≤ n
子任务
测试点编号 | \(n\leq\) | 特殊性质 |
---|---|---|
\(1\sim 3\) | \(17\) | \(k=1\) |
\(4\sim 6\) | \(17\) | \(l_i\leq l_{i+1}\),\(r_i\leq r_{i+1}\) |
\(7\sim 13\) | \(17\) | 无特殊性质 |
\(14\sim 16\) | \(10^2\) | \(k=1\) |
\(17\sim 19\) | \(10^2\) | \(l_i\leq l_{i+1}\),\(r_i\leq r_{i+1}\) |
\(20\sim 25\) | \(10^2\) | 无特殊性质 |
\(26\sim 28\) | \(5\times 10^3\) | \(k=1\) |
\(29\sim 30\) | \(5\times 10^3\) | \(l_i\leq l_{i+1}\),\(r_i\leq r_{i+1}\) |
\(31\sim 41\) | \(5\times 10^3\) | 无特殊性质 |
\(42\sim 43\) | \(5\times 10^4\) | \(k=1\) |
\(44\sim 46\) | \(5\times 10^4\) | \(l_i\leq l_{i+1}\),\(r_i\leq r_{i+1}\) |
\(47\sim 55\) | \(5\times 10^4\) | 无特殊性质 |
\(56\sim 58\) | \(10^5\) | \(k=1\) |
\(59\sim 64\) | \(10^5\) | \(l_i\leq l_{i+1}\),\(r_i\leq r_{i+1}\) |
\(65\sim 76\) | \(10^5\) | \(r_i-l_i<10\) |
\(77\sim 83\) | \(10^5\) | 无特殊性质 |
\(84\sim 90\) | \(10^6\) | \(r_i-l_i<10\) |
\(91\sim 92\) | \(10^6\) | \(k=1\) |
\(93\sim 94\) | \(10^6\) | \(l_i\leq l_{i+1}\),\(r_i\leq r_{i+1}\) |
\(95\sim 100\) | \(10^6\) | 无特殊性质 |
题目关键点
- 问题本质:选择尽可能多的任务,使得在任何时刻最多有 ( k ) 个任务同时进行(任务在结束时刻不计入进行中)。
- 核心约束:任务的时间区间 ([l_i, r_i]) 不能重叠超过 ( k ) 个,但允许任务在结束时刻立即开始下一个任务(即区间端点不重叠不计入冲突)。
- 数据规模:( n \leq 10^6 ),需要高效算法。
正解思路
题解中提到的正确解决方案是:
- 排序策略:将任务按照结束时间 ( r_i ) 从早到晚排序。这有助于优先安排结束早的任务,为后续任务留出空间。
- 贪心选择:依次考虑每个任务,如果加入后不违反“任何时刻最多 ( k ) 个任务”的约束,则选择该任务。
- 约束检查:检查加入任务后,任务区间 ([l_i, r_i]) 内的同时任务数是否超过 ( k )。这需要动态维护每个时间点的任务数。
- 数据结构优化:使用线段树或堆来高效查询区间最大值和更新任务数。具体来说:
- 线段树:维护时间轴上的任务数,支持区间查询最大值和区间加操作(当加入任务时,将 ([l_i, r_i]) 的任务数加1)。
- 堆优化:由于只需要检查后缀最大值,可以用堆来维护当前进行中的任务结束时间,每次检查时弹出已结束的任务。
正解的时间复杂度为 ( O(n \log n) ) 或 ( O(n \log C) )(其中 ( C ) 是时间范围),能够处理 ( n \leq 10^6 ) 的数据。
做题情况分析
- 暴力解法:最初实现了 ( O(n^2) ) 的暴力解法,即枚举任务组合并检查约束。这种方法在 ( n ) 较大时(如 ( n > 10^4 ))会超时,无法通过所有测试点。
- 问题根源:对 ( k ) 的特殊性不敏感,没有意识到 ( k ) 可以作为优化关键。在暴力解法中,未能将问题转化为贪心选择与数据结构维护,导致无法优化到正解。
- 具体不足:
- 没有使用排序策略来简化问题。
- 没有利用数据结构高效检查区间任务数,而是每次重新计算,造成高复杂度。
- 忽略了题解中提到的“结束时间排序”和“区间查询”的提示。
改进建议
- 转换思路:对于区间选择问题,优先考虑按结束时间排序的贪心策略,这常用于解决区间不重叠或资源限制问题。
- 利用 k 值:当 ( k ) 较小时,可以考虑更简单的优化;但即使 ( k ) 较大,也应使用数据结构维护全局约束。
- 掌握数据结构:熟练运用线段树、堆等数据结构处理区间查询和更新,这是解决大规模数据问题的关键。
- 代码实践:在实现正解时,注意离散化时间点以降低空间复杂度,并小心处理区间端点(如结束时刻不计入)。
通过本题,应加强贪心算法与数据结构的结合应用,避免陷入暴力枚举的思维定式。在类似问题中,及时分析约束条件并选择高效算法是得分的关键。