开发者社区> 微凉秋意> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

贪心策略设计并解决会场安排问题

简介: 贪心策略设计并解决会场安排问题
+关注继续查看

问题描述


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


贪心策略


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


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


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


这里我选取第三种方法


算法设计


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


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


image


代码实现


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


image

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
HLS设计方法论 - 优化硬件函数方法论及流水操作的优化策略
HLS设计方法论 - 优化硬件函数方法论及流水操作的优化策略
23 0
工作中的设计模式 —— 策略模式
策略模式是一种行为设计模式,它能让你定义一系列算法,并将每种算法分别放入独立的类中,以使算法的对象能够相互替换。
77 0
asp.net关于WEB端用户重复提交问题。禁用服务器控件按钮问题。
之前也经常遇到这种问题。但是没有去刻意研究并解决。也知道有很多解决方案。但是都没有去亲自实现。直到现在工作中出现这个棘手问题,才去寻找各种解决方案并研究。 还好网上有很多前辈的经验。现在问题算是解决了。因此做个笔记以防后面还会遇到此种问题。虽然这个解决方法不一定很好,但是还是可以实现的。 点击一个按钮,只让此按钮的事件执行一次,防止用户多次点击,造成多次提交数据。因为此事件的方法执行需
1201 0
ASP.NET网站国际化策略
1          问题提出 现在很多网站项目开发要求同时支持多国语言,所以在用户界面及程序的设计和开发中需采取国际化策略,以达到代码改动量小、网站部署便利,用户群广泛的目的。   2          解决策略 .NET Framework 为开发全球通用的应用程序提供了广泛的支持。
842 0
+关注
微凉秋意
以码为梦,步步为营
文章
问答
文章排行榜
最热
最新
相关电子书
更多
典型业务逻辑漏洞挖掘
立即下载
《前端智能化实践》——逻辑代码生成
立即下载
反作弊技术架构与设计
立即下载