2026年上半年软件设计师案例模拟题合集

活动选择问题是指若干个具有竞争性的活动要求互斥使用某一公共资源时，如何选择最大的相容活动集合。假设有一个需要使用某一资源（如场地等）的N个活动组成的集合S={a1, a2, ... , an}，该资源一次只能被一个活动占用。每个活动ai有一个开始时间si和结束时间fi，且0≤si≤fi＜∞。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果两个活动ai和aj的时间区间互不重叠，则称活动ai和aj是兼容的。活动选择问题就是要选择出一个由互相兼容的活动组成的最大子集合。考虑下表中的活动集合，其中各活动采用归并排序算法进行递增排序。从表中可以看到，子集{a3,a9,a11}由相互兼容的活动组成。然而，它不是最大的子集，子集{a1,a4,a8,a11}更大，事实上，{a1,a4,a8,a11}是一个最大的相互兼容活动子集。另外，还有一个最大子集是{a2,a4,a9,a11}

定义集合sij={ak∈s:fi≤sk＜fk≤sj}。为了完整地表示问题，加入两个虚拟活动， a0和an+1，其中，f0=0,sn+1=∞，这样s =s0,n+1。

对于任一非空子问题sij，设am是sij中具有最早结束时间的活动。那么：

（1）活动am在sij的某个最大兼容活动子集中。

（2）子活动sim为空，所以选择am将使smi为唯一可能非空的子问题。

如需了解更多备考资料，可点击下方资料下载处或联系在线客服获取。