简单课程安排问题

问题描述：假定某大学有门课程需要使用同一个教室来上课。显然，我们不能在一个教室同时上两门或多门课程。因此，每门课使用教室的方式是独享的。假定这n门课程的集合为C={c₁,c₂,...,c_n}。每门课使用教室的时间为{s_i,f_i}，i=1,2,...,n。这里s_i=开始时间，f_i=结束时间。假设我们的目标是容纳尽可能多的课程门数，请你为此设计一个算法。

算法设计：

程序实现：

 1 #include<iostream>
 2 
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 struct act // si fi是同一课程的开始和结束时间,用结构体数组存储表示
 8 
 9 {
10 
11 int si ;
12 
13 int fi ;
14 
15 };
16 
17 bool cmp(act a,act b) //比较各门课程结束时间
18 
19 {
20 
21 return a.fi < b.fi;
22 
23 }
24 
25 void greedychoose(int n,act a[])
26 
27 {
28 
29 int count=1,i=0; //初始化,将第一个活动放入a[0]
30 
31 for( int j=1;j<n;j++ ) //往下依次找,若当前课程开始时间大于等于上一门课程的结束时间则选择
32 
33 {
34 
35 if(a[j].si>=a[i].fi)
36 
37 {
38 
39 i=j;
40 
41 count++;
42 
43 }
44 
45 }
46 
47 cout <<"选择的活动数量为:"<< count << endl ;
48 
49 }
50 
51 int main()
52 
53 {
54 
55 int n;
56 
57 cout << "请输入活动数目" <<endl;
58 
59 cin >> n ;
60 
61 act a[20] ;
62 
63 cout << "请依次输入活动的开始时间和结束时间"<<endl;
64 
65 for(int i=0;i<n;i++)
66 
67 {
68 
69 cin >> a[i].si >> a[i].fi ;
70 
71 }
72 
73 sort(a,a+n,cmp);
74 
75 cout<<"按结束时间升序排序结果为:"<<endl;
76 
77 for(int j=0;j<n;j++)
78 
79 {
80 
81 cout << "si="<< a[j].si << " " << "fi=" << a[j].fi << endl ;
82 
83 }
84 
85 greedychoose(n,a);
86 
87 return 0;
88 
89 }

结果输出：