设讲座 j j j开始时间为 s j s_j sj，结束时间为 f j f_j fj。目标：寻找最少的教室数目能安排完所有讲座，保证没有两个讲座在同一时间出现在同一教室。 如下图，表示10个讲座被安排在了4间教室中： 实际更好的安排方案是，将10个讲座按照下图的方式分配到3间教室中：
按照讲座的开始时间由早到晚进行排序，若不兼容则安排到下一间教室中，兼容则安排到本间教室的随后时段，直到安排完所有讲座为止 首先证明该贪心策略的时间复杂度为 n l o g n nlogn nlogn
用一个优先队列来存储教室节点，每个教室节点维护该教室此时最后一个讲座结束时间的属性，并按照该属性维护一个小顶堆性质的优先队列。每个讲座先和优先队列首元素进行比较，若该讲座开始时间 s j s_j sj比队首教室最后一个讲座结束时间早，则新入队一个教室节点，并把该节点最后一个讲座结束时间设为 f j f_j fj。若该讲座开始时间 s j s_j sj大于或等于队首教室最后一个讲座结束时间，则把队首教室最后一个讲座结束时间更新为 f j f_j fj。因为有 n n n个讲座，因此插入或者更新操作的次数为n次，每次复杂度为 l o g n logn logn，总共为 n l o g n nlogn nlogn按照开始时间排序 n n n讲座的时间复杂度为 n l o g n nlogn nlogn综上：总的时间复杂度为 n l o g n nlogn nlogn== 一个事实 == 我们将所有时间点对应的区间数量(具体为该时间点可并行发生的讲座数量)的最大值，叫做深度。 易得：所需教室的数量 ≥ \geq ≥深度 基于上述事实，我们只需证明我们的贪心策略得到的教室数量始终等于深度的，即我们解的下界。就可说明我们的贪心解就是最优解。 证明：
我们设贪心算法所得的教室总数为 d d d之所以需要开放第 d d d个教室，是因为存在一个讲座 j j j，与之前其他 d − 1 d-1 d−1个教室都有一个讲座不兼容因此算上自身，共有 d d d个讲座的结束时间 > s j >s_j >sj贪心策略又是按照开始时间从早到晚开始排序的，因此与讲座 j j j不兼容的 d − 1 d-1 d−1个讲座的开始时间 ≤ s j \leq s_j ≤sj因此这 d d d个讲座必定都包含了某个为 s j + ϵ s_j+\epsilon sj+ϵ的时间点，即至少需要安排 d d d个教室才行综上：我们找到了一个至少需要 d d d个教室的证据，而贪心策略找的教室数正好为下界 d d d，因此贪心解为最优解