如何用贪心算法解决长尾词的会场安排或区间选点问题？

本文共计1930个文字，预计阅读时间需要8分钟。

学习算法课程后的第一次记录，逐渐增加的程序设计考题因素，程序=数据结构+算法，这个等式让我深入体会。从简单的C++编程开始，再到选择合适的算法和数据结构，现在需要更进一步。

学习算法课程之后的第一次记录，渐渐的，程序设计考虑的因素增多，程序=数据结构+算法，这个等式让我深有体会。从开始简单的C++编程，再到选择合适数据结构，现在需要更进一步，从算法层次上考虑程序执行的效率。我对算法的理解是用更少的开销获得更优的执行效果。

分治法、动态规划在此之前没有记录下来，学到贪心算法的时候，觉得需要总结一下学过的东西，也能更好的理解。动态规划的设计，要满足最优子结构性质和重叠子问题，采用自底向上的策略，计算出最优值，找到整体最优解。这个过程有时候挺难的，主要在写出递归式，要自底向上填表。贪心策略有点像动态规划，但在一些方面是不同的，有时候贪心算法的思想更容易想到。它要满足子问题最优而得到整体最优？两个条件：最优子结构性质和贪心选择性质。满足贪心选择性质一定满足最优子结构性质，而满足最优子结构性质不一定满足贪心选择性质，比如背包问题可以用贪心算法解决，而0-1背包问题只能用动态规划。

典型的贪心问题活动安排，有n个活动，给出开始时间和结束时间，要尽可能安排多的活动（时间互相不冲突）。解决这个问题正确的贪心思想是以每个活动结束时间为比较变量，按结束时间升序排好活动次序，接着就进行比较选择。而会场安排问题与活动又有些不同之处，下面是我的解题过程。

7-2 会场安排问题 (20 分)

假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的 贪心算法进行安排。（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个 顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小 会场数。