本文共 3845 字，大约阅读时间需要 12 分钟。
今天学习了贪心。
//上午做的感觉太差了。。。
需要整理一下
下午贪心也没听听懂。
贪心之二：教室活动安排问题
有若干个活动，第i个开始时间和结束时间是[Si,fi)，活动之间不能交叠，要把活动都安排完，至少需要几个教室？
输入
第一行一个正整数n (n <= 10000)代表活动的个数。
第二行到第(n + 1)行包含n个开始时间和结束时间。
开始时间严格小于结束时间，并且时间都是非负整数，小于1000000000
输出
一行包含一个整数表示最少教室的个数。
输入示例
3
1 2
3 4
2 9
输出示例
2
参考代码
这是要解决什么问题呢？
我一定要调试才明白么。。。。
算了，刚开始，多理解一些，否则画的时间太久了。
#include #include #include #include using namespace std;set sta, ed;int l[10005], r[10005], a[20010];// 先开数组int main(){ int n, k=0; cin>>n; for(int i=0; i >l[i]>>r[i]; sta.insert(l[i]); ed.insert(r[i]); }// 输入两个数据，分别是开始时间和结束时间//【insert是啥】// 【已 输入完成，输入完成，输入完成】 int len=0; for(int i=0; i
这个其实很，非常形象，就是把它变成三个队列一样的，
a[i]是有序的，，询问这些是否
如果相等，他是不可能先开始马上又结束的，所以++ -- 就回去了
如果在ed里面
因为是有序的，肯定要先开始再结束，所以先把st提取出来，
k就相当于是在并行的作用。
因为肯定是先开始再结束，里面其实默认了一个关系，也就是说end的肯定是st里面的end
这个就是生活常理了。
这样，就非常形象鲜明的
而且并行的意思就是如果执行完成走到他家那个end了，k减去，标记可以重新开始。
题意理解完成，接下来自己打一份这个代码。
( 打核心部分)
1、#include<algorithm>
包含max（），sort（）
2、贪心需要用到 优先队列，和sort（）默认 是升序，由小到大
3、ans = max(ans, k);所曾经达到的最多的。这个用法不错，记一下。
【借鉴】
4、输入1 5 2 8 3 9 的次序，记录并存储的话可以；
先有两个数组存一下，然后
int len = 0; for (int i = 0; i
（比较快了）(但应该不是最好的，只是针对这个题目而言)5、数组初始化memset(a,0,sizeof(a));for (int i=0;i<n;i++) a[i]=06、struct node{int start;int end;}a[11111];定义时还是有 a[i].start()种种。7、end = -1e9 - 100;嗯，写到这里，我才发现tmd sta和ed是set，因为那个insert。关于set，必须说明的是set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型，并且能从一个数据集合中取出数据，在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变。count() 用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了。【贪心之一】贪心之一 有若干个活动，第i个开始时间和结束时间是[Si,fi)，只有一个教室，活动之间不能交叠，求最多安排多少个活动？分析： 我们就是想提高教室地利用率，尽可能多地安排活动。考虑容易想到的几种贪心策略：【下面找到的这个代码和学长上课的时候讲的 比较像】标准的贪心 用到结构体（sort重载）、优先队列什么的。sort（）如果想按照其他标准进行排序，就需要提供比较函数，该函数要比较两个值，然后返回一个用于说明这两个值的相对顺序的数字。比较函数应该具有两个参数 a 和 b，其返回值如下：若 a 小于 b，在排序后的数组中 a 应该出现在 b 之前，则返回一个小于 0 的值。若 a 等于 b，则返回 0。 (此时不排序)若 a 大于 b，则返回一个大于 0 的值。*****结构体的排序顺序:首先按照a.x递增的方式排序。若a.x相同，则按照b.y的递增方式排序。对应代码：
bool cmp(node x, node y){ if (x.end y.start) return true; return false;} 优先的是 y结束的早（end值大）
或者，他们都一样时间结束，但是x开始的晚（时间更少）
代码粘贴
#include #include #include #include using namespace std;struct node{ int start; int end;} a[11111];bool cmp(node x, node y){ if (x.end y.start) return true; return false;}int main(){ int n, i, j, ans, end; cin >> n; for (i = 0; i > a[i].start >> a[i].end; sort(a, a + n, cmp); // 是重载了结构体之后进行的排序// 也就是说！重载之后的 //也就是说！按结束时间排序的 // 唉 有不会的 懂了 自然好 可是你不会的太多了 还得加把劲啊。 // 可是你不会的太多了！划重点！已经八点钟了，还是只看了一个题啊！一直在吃而已吧！！！！ /// 哦。。还有跟他聊天（哈哈哈 ans = 0; end = -1e9 - 100; for (i = 0; i = end)//从最开始，这个是肯定成立着的，然 { ans++;// 结束时间最早的这个，end值存一下 //就算他不是结束时间最早的，（要是有人跟他相等） //没有就算。。已经重载过了，如果相等那么按x返回，肯定是最短的 // 所以无形之中其实排序起了很大的作用 end = a[i].end; } // 然后第二个a[i]， 判断a[i].start >= end // 就是 第二小的有没有在他结束的时候ojbk //如果有当然很好，如果没有也没关系 //每次push进去一个，ans用来记录。 } cout << ans << endl; return 0;}
原文地址：http://blog.csdn.net/h1021456873/article/details/49076243
（4） 看似最不对的策略——结束时间越早的活动优先。这个策略是有效的，我们可以证明。假设最优解OPT中安排了m个活动，我们把这些活动也按照结束时间由小到大排序，显然是不冲突的。假设排好顺序后，这些活动是a(1) , a(2), a(3)….am
假设按照我们的贪心策略，选出的活动自然是按照结束时间排好顺序的，并且也都是不冲突的，这些活动是b(1), b(2) …b(n)
【选出的】
问题关键是，假设a(1) = b(1), a(2) = b(2)…. a(k) = b(k)，但是a(k+1) != b(k+1)，回答几个问题：
【在k以及k之后，他们不同了】
【f(b(k+1)) <= f(a(k+1))】
【b是最优 a是排好序的】
(1)b(k+1)会在a(k+2), a(k+3), …. a(m)中出现么？
不会。因为b(k+1)的结束时间是最早的，即f(b(k+1)) <= f(a(k+1)),而a(k+2), a(k+3), …. a(m)的开始时间和结束时间都在f(a(k+1))之后，所以b(k+1)不在其中。
(2)b(k+1)和a(1), a(2), …. a(k) 冲突么？
不冲突，因为a(1), a(2), …. a(k)就是b(1), b(2), …. b(k)
(3)b(k+1)和a(k+2), a(k+3), …. a(m)冲突么？
不冲突，因为f(b(k+1)) <= f(a(k+1))，而a(k+2), a(k+3), …. a(m)的开始时间都在f(a(k+1))之后，更在f(b(k+1))之后。
因此我们可以把a(k+1) 换成b(k+1)， 从而最优解和我们贪心得到的解多了一个相同的，经过一个一个替换，我们可以把最优解完全替换成我们贪心策略得到的解。 从而证明了这个贪心策略的最优性。
最后，我们来提供输入输出数据，由你来写一段程序，实现这个算法，只有写出了正确的程序，才能继续后面的课程。