【贪心法】会场安排问题

简介: 【贪心法】会场安排问题

  问题描述:

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

编程任务:

  对于给定的k 个待安排的活动,编程计算使用最少会场的时间表。

数据输入:

  (由文件input.txt 给出输入数据。)第一行有1 个正整数k,表示有k 个待安排的活动。接下来的k 行中,每行有2 个正整数,分别表示k 个待安排的活动开始时间和结束时间。时间以0 点开始的分钟计。

结果输出:

  将编程计算出的最少会场数输出(到文件output.txt 。)

注:若题目含上述括号中橙色字体,将代码第11、12行注释解除,令其执行即可

代码如下:

#include <iostream>
#include <fstream>//文件操作头文件 
#include <algorithm>//sort()函数头文件 
using namespace std;
#define N 100000
bool cmp(int x,int y){
  return x<y;
}
int main(){
  //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
  int n;cin>>n;//n:活动个数
  int begin[N],end[N];//活动起止时间 
  int AreaNum=0;//所需会场个数 
  for(int i=0;i<n;i++){
    cin>>begin[i]>>end[i];
  }
  sort(begin,begin+n,cmp);//对活动开始时间排序 
  sort(end,end+n,cmp);//对活动结束时间排序 
  int j=0;  
  for(int i=0;i<n;i++){
    if(begin[i]<end[j]) AreaNum++;//活动i开始时间小于结束时间[j],创建新会场 
    else j++;//将第i个活动加入end[j]后
  }
  cout<<AreaNum<<endl;
  return 0;
}

image.gif


目录
打赏
0
0
0
0
2
分享
相关文章
非启发式算法——中国剩余定理
非启发式算法——中国剩余定理
140 0
算法提高:组合数学| 容斥原理常见应用
容斥原理常见的问题如下。 (1) 篮球、羽毛球、网球三种运动,至少会一种的有22人,会篮球的有15人,会羽毛球的有17人,会网球的有12人,既会篮球又会羽毛球的有11人,既会羽毛球又会网球的有7人,既会篮球又会网球的有9人,那么三种运动都会的有多少人? (2) 《西游记》《三国演义》《红楼梦》三大名著,至少读过其中一本的有20人,读过《西游记》的有10人,读过《三国演义》的有12人,读过《红楼梦》的有15人,读过《西游记》《三国演义》的有8人,读过《三国演义》《红楼梦》的有9人,读过《西游记》《红楼梦》的有7人。问三本书全都读过的有多少人?
200 0
算法提高:组合数学| 容斥原理常见应用
【算法学习】—n皇后问题(回溯法)
【算法学习】—n皇后问题(回溯法)
算法提高:组合数学| 卡特兰数的实现
卡特兰数列是组合数学中在各种计数问题中常出现的数列,其前几项为1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012…… 卡特兰数首先是由欧拉在计算对凸n边形的不同的对角三角形剖分的个数问题时得到的,即在一个凸n边形中,通过不相交于n边形内部的对角线,把n边形拆分成若干三角形,不同的拆分数用Hn表示,Hn即卡特兰数。
159 0
算法提高:组合数学| 卡特兰数的实现
质数筛法:朴素素数筛,埃氏筛,欧式筛
质数筛法:朴素素数筛,埃氏筛,欧式筛
174 0
算法简单题,吾辈重拳出击 - 动态规划之爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
【算法】 八皇后问题之回溯法
会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 * 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。每次填满第一行第一列,当不满足时候,试下第一行第二列,依次进行,递归的出口为找到第八个点,跳出递归。,在循环里面还要判断是否满足不同行,不同列,不同对角线。使用回溯法来解决该问题,下面的代码是我看到过的最精简的代码,相关的注释都写在代码上了。运行得出结果,总共有92中结果。
284 0
爬楼梯(动态规划)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
73 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等