C++超详细讲解贪心策略的设计及解决会场安排问题

目录
  • 问题描述
  • 贪心策略
  • 算法设计
  • 代码实现
    • 选择结构体
    • 随机输入会议
    • 按结束时间排序
    • 最终会议确定
  • 结束语

问题描述

设有n个会议的集合C={1,2,…,n}，其中每个会议都要求使用同一个资源（如会议室），而在同一时间内只能有一个会议使用该资源。每个会议i都有要求使用该资源的起始时间bi和结束时间ei，且bi < ei 。如果选择了会议i使用会议室，则它在半开区间[bi, ei)内占用该资源。如果[bi, ei)与[bj , ej)不相交，则称会议i与会议j是相容的。会场安排问题要求在所给的会议集合中选出最大的相容活动子集，也即尽可能地选择更多的会议来使用资源。

贪心策略

1、选择最早开始时间且不与已安排会议重叠的会议

2、选择使用时间最短且不与已安排会议重叠的会议

3、选择具有最早结束时间且不与已安排会议重叠的会议

这里我选取第三种方法

算法设计

设有11个会议等待安排，用贪心法找出满足目标要求的会议集合。这些会议按结束时间的非减序排列如表所示

11个会议按结束时间的非减序排列表：

代码实现

#include <iostream>
#include "会场安排.h"
#define n 11
struct meeting{
	int B;//开始时间
	int E;//结束时间
};
using namespace std;
int main()
{
	meeting M[n] = { {8,11}, {8,12}, {2,13}, {12,14}, {1,4},
		           {3,5}, {0,6}, {5,7}, {3,8}, {5,9}, {6,10} };
	for(int i=0;i<n;i++)
		for(int j=0;j<n-i-1;j++)
			if (M[j].E > M[j + 1].E) {
				meeting T;
				T = M[j]; M[j]= M[j+ 1]; M[j+1]= T;
			}
	int allowedTime = 0;
	for (int i = 0,j=0; i < n; i++) {
		if (M[i].B > allowedTime) {
			j++;
			cout << "安排的第"<<j<<"个会议号是 " << i+1 <<" 此会议开始时间为：" << M[i].B
				<<" 此会议结束时间是：" << M[i].E << endl;
			allowedTime = M[i].E;
		}
	}
}

选择结构体

定义meeting结构体，只设置会议开始时间B和结束时间E即可。

随机输入会议

n 为11

meeting M[n] = { {8,11}, {8,12}, {2,13}, {12,14}, {1,4},

{3,5}, {0,6}, {5,7}, {3,8}, {5,9}, {6,10} };

按结束时间排序

冒泡排序实现即可：

for(int i=0;i<n;i++)

for(int j=0;j<n-i-1;j++) if (M[j].E > M[j + 1].E)

{

meeting T; T = M[j]; M[j]= M[j+ 1]; M[j+1]= T;

}

这里的中间变量必须设置为 meeting 类型，以便于将会议的所有属性都交换

最终会议确定

int allowedTime = 0;
    for (int i = 0,j=0; i < n; i++) {
        if (M[i].B > allowedTime) {
            j++;
            cout << "安排的第"<<j<<"个会议号是 " << i+1 <<" 此会议开始时间为：" << M[i].B 
                <<" 此会议结束时间是：" << M[i].E << endl;
            allowedTime = M[i].E;
        }
    }

先将会议开始时间设置为0，只要把按结束时间升序排列的第一个大于0的开始时间加到第一个内容哦即可，随后将第一个会议的结束时间设置为allowedTime，产生下一个不与第一个会议时间冲突的会议；然后自己加点输出语句，美观的运行出来结果就好了。

结束语

这算是贪心法第一个案例，也是比较好理解的一个案例，希望大家分析后都能有自己的收获，下篇博客再见，觉得好就鼓励鼓励博主吧

到此这篇关于C++超详细讲解贪心策略的设计及解决会场安排问题的文章就介绍到这了,更多相关C++贪心策略内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言详细分析贪心策略中最小生成树的Prime算法设计与实现

    C语言详细分析贪心策略中最小生成树的Prime算法设计与实现

    目录 浅析最小生成树 Prime算法思想 此算法核心部分 结构体的选择 实现思路 构造实例 构造过程 代码详解 调试结果 总结 浅析最小生成树 设G=(V,E)是无向连通带权图.E中每条边(v,w)的权为c[v][w]. 生成树:如果G的子图G’是一棵包含G的所有顶点的树,则称G’为G的生成树. 耗费:生成树上各边权的总和 最小生成树:在G的所有生成树中,耗费最小的生成树最小生成树在实际中有广泛应用. 例如,在设计通信网络时,用图的顶点表示城市,用边(v,w)的权c[v][w]表示建立城市v和城

  • C++超详细讲解贪心策略的设计及解决会场安排问题

    C++超详细讲解贪心策略的设计及解决会场安排问题

    目录 问题描述 贪心策略 算法设计 代码实现 选择结构体 随机输入会议 按结束时间排序 最终会议确定 结束语 问题描述 设有n个会议的集合C={1,2,…,n},其中每个会议都要求使用同一个资源(如会议室),而在同一时间内只能有一个会议使用该资源.每个会议i都有要求使用该资源的起始时间bi和结束时间ei,且bi < ei .如果选择了会议i使用会议室,则它在半开区间[bi, ei)内占用该资源.如果[bi, ei)与[bj , ej)不相交,则称会议i与会议j是相容的.会场安排问题要求在所给的会

  • 四个实例超详细讲解Java 贪心和枚举的特点与使用

    四个实例超详细讲解Java 贪心和枚举的特点与使用

    目录 贪心: 枚举: 1.朴素枚举 2.状压枚举    算法题1: 示例 算法题2: 示例 算法题3:  示例1 示例2 算法题4:  示例1 笔试技巧:学会根据数据范围猜知识点          一般1s 时间限制的题目,时间复杂度能跑到 1e8 左右( python 和 java 会少一些,所以建议大家使用c/c++ 做笔试题). n 范围 20 以内: O(n*2^n) 状压搜索 /dfs 暴搜 n 范围 200 以内: O(n^3) 三维 dp n 范围 3000 以内: O(n^2)

  • 四个实例超详细讲解Java 贪心和枚举的特点与使用

    四个实例超详细讲解Java 贪心和枚举的特点与使用

    目录 贪心: 枚举: 1.朴素枚举 2.状压枚举 算法题1: 示例 算法题2: 示例 算法题3: 示例1 示例2 算法题4: 示例 笔试技巧:学会根据数据范围猜知识点 一般1s 时间限制的题目,时间复杂度能跑到 1e8 左右( python 和 java 会少一些,所以建议大家使用c/c++ 做笔试题). n 范围 20 以内: O(n*2^n) 状压搜索 /dfs 暴搜 n 范围 200 以内: O(n^3) 三维 dp n 范围 3000 以内: O(n^2) 二维 dp 背包 枚举 二维前

  • 超详细讲解Java线程池

    超详细讲解Java线程池

    目录 池化技术 池化思想介绍 池化技术的应用 如何设计一个线程池 Java线程池解析 ThreadPoolExecutor使用介绍 内置线程池使用 ThreadPoolExecutor解析 整体设计 线程池生命周期 任务管理解析 woker对象 Java线程池实践建议 不建议使用Exectuors 线程池大小设置 线程池监控 带着问题阅读 1.什么是池化,池化能带来什么好处 2.如何设计一个资源池 3.Java的线程池如何使用,Java提供了哪些内置线程池 4.线程池使用有哪些注意事项 池化技术

  • C++函数模板与重载解析超详细讲解

    目录 1.快速上手 2.重载的模板 3.模板的局限性 4.显式具体化函数 5.实例化和具体化 6.重载解析 6.1 概览 6.2 完全匹配中的三六九等 6.3 总结 7.模板的发展 1.快速上手 函数模板是通用的函数描述,也就是说,它们使用泛型来定义函数. #include<iostream> using namespace std; template <typename T> void Swap(T &a,T &b);//模板原型 struct apple{ st

  • 超详细讲解Linux C++多线程同步的方式

    目录 一.互斥锁 1.互斥锁的初始化 2.互斥锁的相关属性及分类 3,测试加锁函数 二.条件变量 1.条件变量的相关函数 1)初始化的销毁读写锁 2)以写的方式获取锁,以读的方式获取锁,释放读写锁 四.信号量 1)信号量初始化 2)信号量值的加减 3)对信号量进行清理 背景问题:在特定的应用场景下,多线程不进行同步会造成什么问题? 通过多线程模拟多窗口售票为例: #include <iostream> #include<pthread.h> #include<stdio.h&

  • C++ 数据结构超详细讲解单链表

    C++ 数据结构超详细讲解单链表

    目录 前言 一.链表是什么 链表的分类 二.链表的实现 总结 (❁´◡`❁) 单链表 前言 上篇顺序表结尾了解了顺序表的诸多缺点,链表的特性很好的解决了这些问题,本期我们来认识单链表. 一.链表是什么 链表是一种物理存储结构上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接依次实现的. 由图,链式结构在逻辑上是连续的,但是物理上不一定连续 显示中结点一般是从堆上申请出来的 从堆上申请的空间,是按照一定的策略划分的,两次申请的空间,可能连续,可能不连续,见顺序表 链表的分类 链表

  • Java 超详细讲解设计模式之中的抽象工厂模式

    Java 超详细讲解设计模式之中的抽象工厂模式

    目录 抽象工厂模式 1.什么是抽象工厂 2.抽象工厂模式的优缺点 3.抽象工厂模式的结构与实现 4.抽象工厂方法模式代码实现 5.抽象工厂模式的应用场景 6.抽象工厂模式的扩展 抽象工厂模式 前面文章介绍的工厂方法模式中考虑的是一类产品的生产,比如案例中的百事可乐工厂只能生产百事可乐,可口可乐工厂只能生产可口可乐,也就是说:工厂方法模式只考虑生产同等级的产品. 1.什么是抽象工厂 在现实生活中许多工厂是综合型的工厂,能生产多种类)的产品,就拿案例里面的可乐来说,在节日的时候可能会有圣诞版的可乐,

  • Java超详细讲解设计模式之一的工厂模式

    Java超详细讲解设计模式之一的工厂模式

    目录 工厂模式 1.简单工厂 1.1结构 1.2实现 1.3优缺点 1.4扩展 2.工厂方法 2.1结构 2.2实现 2.3优缺点 3.抽象工厂 3.1结构 3.2实现 3.3优缺点 4.模式扩展 4.1实现 工厂模式 在Java应用程序中对象无处不在,这些对象都需要进行创建,如果创建的时候直接new对象,那么如果我们要更换对象,所有new对象的地方都需要进行更改.违背了软件设计原则中的开闭原则.如果我们使用工厂生产对象,只需要在工厂中关注对象的改变即可,达到了与对象解耦的目的,工厂模式最大的特

随机推荐