基本信息

---

下载

文档摘要

---

2025年ccf考试题库及答案

一、项目选择问题

某公司有n个待选项目，每个项目i有开始时间s_i、结束时间e_i（s_ie_i，时间单位为整数）和利润p_i（p_i0）。若两个项目的时间区间有重叠（即一个项目的开始时间小于另一个的结束时间），则无法同时选择。要求选择若干不重叠的项目，使得总利润最大。n≤1e5，s_i、e_i≤1e9。

答案

1.解题思路：

该问题为经典的带权区间调度问题，需用动态规划结合二分查找优化。核心思想是按结束时间排序，对于每个项目i，找到最后一个不与i冲突的项目j（即e_j≤s_i），则最大利润为max（不选i时的最大利润，选i时的利