贪心方法，动态规划法，分治法有类似之处，都需要将问题划分为一个个子问题，然后通过解决这些子问题来解决最终问题。
贪心方法是把多阶段过程转化为一系列单阶段问题，然后求解各阶段问题的最优解，将各阶段的最优解合起来最终求得原问题的最优解。
因为有些问题的阶段最优解合起来并不是整体的最优解，因此贪心方法并不能对所有问题适用，它只适用于当前阶段问题的最优解并不会影响之前阶段的问题的解。
问题：有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据时间区间[si,fi]。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。求解安排这些活动使得尽量多的活动能不冲突的举行。
第一阶段：选择第一个活动，通过问题分析选择第一个活动可以通过3种方式进行选择；
1、选择开始时间最早的活动；若开始时间最早但是确占用了所有时间，则只能安排一个活动，因此该方式并不是最优。
2、选择占用时间最短的活动；若占用时间最短的活动是当天的最后一段时间，则也只能安排一个活动，因此该方式并不是最优。
3、选择结束时间最早的活动；结束时间最早代表后面能继续安排活动的机会越大，因此该方式是最优的。
通过第3种方式的选择，选择第一个活动的最优解ai=1。
第二阶段：选择第二个活动,第二个活动的选择方式同一阶段，但是需保证，第二个活动的起始时间大于第一个活动的结束时间【该阶段的解不影响前阶段的解】，同时第二个活动的结束时间是最早的【最优解】。
第三阶段：选择第三个活动，同二阶段。
第四阶段：选择第四个活动。
根据这个四个阶段的最优解，得到整个问题的最优解使用上表的活动安排方式，能使得当天的活动安排达到最多。
閱讀更多 志趣空間 的文章
