问题

给出若干个节目在同一个舞台演出，每个节目需要占用一段时间的舞台，用起始时间和结束时间表示。
不同的节目占用舞台的时间不可以有重叠，如何安排可以被安排上的节目数量最多。

解析

对所有节目按照结束时间升序排列，按顺序排列不冲突的节目，最终得到的就是不冲突节目数量最多的安排
证明：

  • 定理1：设时间区间的最优解为,,其中一定是区间的最优解
    • 证明：
    • 若不是区间的最优解，则存在,显然,这与是最优解相悖，所以一定是区间的最优解
  • 定理2：设是区间中最早结束的事件，则在区间的其中一个最优解中
    • 证明：
    • 设区间的一个最优解为,若事件是中最先发生的一个事件，事件为区间内最早结束的事件，结束时间为记作，则
      • 若，则与结论相符合
      • 若,则的结束事件必然,用替换不影响解的相容性，所以也是区间的一个最优解
  • 证明：贪心的选择最早结束的事件能够组成最优解;数学归纳法证明如下
    • 由定理2可知，最早结束的第一个事件一定属于最优解之一
    • 假设已知前个事件的最优解为,则:由定理1可知,再由定理2，结束时间最早的事件必然是的一部分，所以

得证

其他贪心策略

  • 按起始时间升序，反例：{{1，100}，{2，2}，{3，3}，{4，4}}
  • 按占用时间升序，反例：{{3,4},{1,3},{4,10}}

设计

  • a.sort(key=finishTime)
  • pre=-1,S=
  • for e in a:
  • if e.startTime>pre:
  • pre=e.finishTime,S.append(e)
  • return S

分析

排序的复杂度为
枚举的复杂度为
总复杂度为

源码

传送门