本文主要是介绍算法导论第16章练习题 16.1-4，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
16.1-4 假设有一组活动，我们需要将它们安排到一些教室，任意活动都可以在任意教室进行。我们希望使用最少的教室来完成活动。设计一个高效的贪心算法，求每个活动应该在哪个教室来进行。
（这个问题也被称为区间图着色问题。我们可以作出一个区间图，其顶点为已知的活动，其边连接着不兼容的活动。要求使用最少的颜色对顶点进行着色，使得所有相邻顶点颜色均不相同——这与使用最少的教室完成所有的活动的问题是对应的。）
下面内容翻译于算法导论教师手册的练习题答案（翻了个大意，可能会有翻译的不准确的地方）。
解答：
设S是n个活动的集合。
“显而易见”的解法是使用前面章节的贪心算法，来找到S中的一个最大兼容活动集合S1，S1中的活动全部放在第1个教室进行，然后在找到S-S1中的另一个最大兼容活动集合S2……（直到所有活动都被分配），最坏时间是Θ（n^2）。此外，有可能得到的教室个数不是最少的。例如：
考虑活动集合{ [1 , 4) , [2 , 5) ,[6 , 7) ,[4 , 8) }。贪心算法会选择[1 , 4)，[6 , 7)放在第一个教室，另外两个活动每个分别是第二第三个教室，一共需要3个教室。而最优解是 [1 , 4) ,[4 , 8) 放在第一个教室，[2 , 5) ,[6 , 7)放在第二个教室，一共需要2个教室。
正确的算法是下面这样，其渐进时间只是将活动按时间来进行排序的时间。
一般的想法是按照活动开始时间进行遍历，把每个活动分配到那个时刻空闲的教室。将每个活动的开始时间和结束时间放在一起按时间排序，然后遍历整个时间表。同时维护两个列表：在时刻t空闲的教室列表（free），和已经安排了活动i的教室列表（busy）（活动i开始时间si<=t , 而且结束时间fi>t）。当t是某个活动的开始时刻时，把该活动分配到一个空闲教室，然后把该教室从free列表中移到busy列表。当t是某个活动的结束时刻时，把该活动分配的教室 ，从busy列表中移到free列表中。
为了避免使用额外不必要的教室，在分配教室时，总是分配已经办过活动的教室，如果没有，再启用新教室（可以通过这样的方式来达到此目的：讲空闲教室从free列表中移出或移进，都在列表头进行）
这就保证了使用尽可能少的教室：这个算法会使用m个教室（m<=n），设活动i是被分配给教室m的第一个活动，活动i在教室m中进行的原因是在活动i开始时间si时，前m-1个教室都有活动在进行。所以此刻一共有m个活动在同时进行。因此任何分配方式都至少需要m个教室，因此这个算法的结果是最优的。
Run Time：
排序2n个时间（n个活动的开始和结束时间）。（若某个活动i的结束时间和另一个活动j的开始时间相同，那么活动i结束时间排在前面，一般是O（nlgn），也可能是O（n））
在O（n）内处理活动：扫描2n个时间点，O（1）维护两个教室列表（free，busy）
Total：O（n+排序时间）
代码如下：
class TimePoint():def __init__(self,n,time,isStart=True,classroom=-1):self.activity=n #活动号self.time=time #时间点self.classroom=classroom #被分配的教室号self.isStart=isStart #是否是开始时间#对时间点排序
def pointSort(timePointList,activityList): n=len(activityList)for i in range(n):timePointList.append(TimePoint(i,activityList[i][0]))timePointList.append(TimePoint(i,activityList[i][1],False))p=sorted(timePointList,key=lambda point: point.time)#使用的python内置sorted进行排序for i in range(2*n-1):#调整时间点相同时，将结束时间排在前面if p[i].time==p[i+1].time and p[i].isStart==True and p[i+1].isStart==False:temp=p[i+1];p[i+1]=p[i];p[i]=tempreturn p#分配过程
def allocation(timePointList,free,busy):classroom=0 #分配的教室最开始是0（没有教室）for timePoint in timePointList: #遍历时间点#如果该时间点是某个活动开始时间if timePoint.isStart==True: if len(free)>0: #如果free非空busy.append(free[0]) #将free中第一个教室移动到busy中timePoint.classroom=free[0] #记录该活动在哪个教室进行（这里只标记了该活动的开始时间点）free.pop(0) #将该教室从free中删除else: #如果free空的classroom+=1 #启用一个新教室busy.append(classroom)timePoint.classroom=classroom#下面的循环是将该活动的结束时间点也标记上在哪个教室进行for x in [ i for i in timePointList if i!=timePoint]:if x.activity==timePoint.activity:x.classroom=timePoint.classroombreakprint 'free',freeprint 'busy',busy#该时间点是某个活动结束时间else:free.insert(0,timePoint.classroom) #将busy中的该活动进行的教室移动到free中的第一个busy.remove(timePoint.classroom) #从busy中删除该教室 print 'free',freeprint 'busy',busyreturn classroom #最后classroom就是所需要的最少教室数if __name__ == '__main__':free=[]busy=[]timePointList=[]activityList=[[1,4],[2,5],[6,7],[4,8],[9,10],[2,3]]timePointList=pointSort(timePointList,activityList)number=allocation(timePointList,free,busy)print number这篇关于算法导论第16章练习题 16.1-4的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
