<算法>贪心策略设计并解决会场安排问题

2023-10-13 13:59

本文主要是介绍<算法>贪心策略设计并解决会场安排问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

🎉 每个不曾起舞的日子都是对生命的辜负

🎉写在前面

期末考试邻近,为了更好的应对《算法设计与分析》这门课程,我把书上以及老师讲过的案例都详细的做一个重现及解剖,让你熟记每一个潜在的考点,希望能给大家帮助。


🎉目录

问题描述

 贪心策略

 算法设计

代码实现

选择结构体

随机输入会议

按结束时间排序

最终会议确定

结束语


问题描述

设有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,产生下一个不与第一个会议时间冲突的会议;然后自己加点输出语句,美观的运行出来结果就好了。

结束语

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

这篇关于<算法>贪心策略设计并解决会场安排问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/203728

相关文章

Java循环创建对象内存溢出的解决方法

《Java循环创建对象内存溢出的解决方法》在Java中,如果在循环中不当地创建大量对象而不及时释放内存,很容易导致内存溢出(OutOfMemoryError),所以本文给大家介绍了Java循环创建对象... 目录问题1. 解决方案2. 示例代码2.1 原始版本(可能导致内存溢出)2.2 修改后的版本问题在

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法:数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高;分治法高效但实现复杂;位图法可读性差,但存储空间受限... 目录三种方法:方法概要数据库排序(http://www.chinasem.cn对数据库设备要求较高)分治法(常

Redis多种内存淘汰策略及配置技巧分享

《Redis多种内存淘汰策略及配置技巧分享》本文介绍了Redis内存满时的淘汰机制,包括内存淘汰机制的概念,Redis提供的8种淘汰策略(如noeviction、volatile-lru等)及其适用场... 目录前言一、什么是 Redis 的内存淘汰机制?二、Redis 内存淘汰策略1. pythonnoe

Vue项目中Element UI组件未注册的问题原因及解决方法

《Vue项目中ElementUI组件未注册的问题原因及解决方法》在Vue项目中使用ElementUI组件库时,开发者可能会遇到一些常见问题,例如组件未正确注册导致的警告或错误,本文将详细探讨这些问题... 目录引言一、问题背景1.1 错误信息分析1.2 问题原因二、解决方法2.1 全局引入 Element

linux报错INFO:task xxxxxx:634 blocked for more than 120 seconds.三种解决方式

《linux报错INFO:taskxxxxxx:634blockedformorethan120seconds.三种解决方式》文章描述了一个Linux最小系统运行时出现的“hung_ta... 目录1.问题描述2.解决办法2.1 缩小文件系统缓存大小2.2 修改系统IO调度策略2.3 取消120秒时间限制3

关于@MapperScan和@ComponentScan的使用问题

《关于@MapperScan和@ComponentScan的使用问题》文章介绍了在使用`@MapperScan`和`@ComponentScan`时可能会遇到的包扫描冲突问题,并提供了解决方法,同时,... 目录@MapperScan和@ComponentScan的使用问题报错如下原因解决办法课外拓展总结@

MybatisGenerator文件生成不出对应文件的问题

《MybatisGenerator文件生成不出对应文件的问题》本文介绍了使用MybatisGenerator生成文件时遇到的问题及解决方法,主要步骤包括检查目标表是否存在、是否能连接到数据库、配置生成... 目录MyBATisGenerator 文件生成不出对应文件先在项目结构里引入“targetProje

C#使用HttpClient进行Post请求出现超时问题的解决及优化

《C#使用HttpClient进行Post请求出现超时问题的解决及优化》最近我的控制台程序发现有时候总是出现请求超时等问题,通常好几分钟最多只有3-4个请求,在使用apipost发现并发10个5分钟也... 目录优化结论单例HttpClient连接池耗尽和并发并发异步最终优化后优化结论我直接上优化结论吧,

Java内存泄漏问题的排查、优化与最佳实践

《Java内存泄漏问题的排查、优化与最佳实践》在Java开发中,内存泄漏是一个常见且令人头疼的问题,内存泄漏指的是程序在运行过程中,已经不再使用的对象没有被及时释放,从而导致内存占用不断增加,最终... 目录引言1. 什么是内存泄漏?常见的内存泄漏情况2. 如何排查 Java 中的内存泄漏?2.1 使用 J

numpy求解线性代数相关问题

《numpy求解线性代数相关问题》本文主要介绍了numpy求解线性代数相关问题,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 在numpy中有numpy.array类型和numpy.mat类型,前者是数组类型,后者是矩阵类型。数组