贪心算法之活动安排问题

前言

最近时间还是比较紧张的，对于算法这一块，网上也有好多大神写了不少这样的文章，我有时候不明白了，看不懂课本，就看看别人写的东西，看得多了，也就懂了一些什么。所以这里，就不再详细的说明活动安排问题的内容，直接上代码。其实书上的算法看明白了，写代码也很轻松的，关于有些衔接部分就需要有更深的领悟。

代码

关于本程序，之前用C语言写了一个，但是不是很方便，因为算法中用到的true false bool类型，有点麻烦，所以我感觉对于算法的实现用c++会比较方便吧。这个看个人喜好，喜欢C语言的就坚持，反正都能解决问题。
C++代码

#include <iostream>
using namespace std;
void  GreedSelector(int n,int s[],int f[],bool A[]);
const int n = 11;
int main()
{
    int s[12]={0,1,3,0,5,3,5,6,8,8,2,12},f[12]={0,4,5,6,7,8,9,10,11,12,13,14};
    bool A[n+1];
    GreedSelector(n,s,f,A);
    cout<<"最大相容活动安排为："<<endl;
    for(int i=1;i<=n;i++)
    {
       if(A[i])
        {
            cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;
        }
    }
 
    return 0;
}
void  GreedSelector(int n,int s[],int f[],bool A[])
{
    A[1]=true;
    int j=1;
    for (int i=2;i<=n;i++)
    {
 
        if(s[i]>=f[j])
    {
        A[i]=true ;
        j=i;
    }
    else
    {
        A[i]=false;
    }
    }
}
C 代码
 
 
#include <stdio.h>
#include <stdlib.h>
typedef int bool;
#define true 1
#define false 0
int  GreedSelector(int n,int s[],int f[],bool A[])
{
    A[1]=true;
    int i,j=1,count=1;
    for (i=2;i<=n;i++)
    {
 
        if(s[i]>=f[j])
    {
        A[i]=true ;
        j=i;
 count++;
    }
    else A[i]=false;
    }
return count;
}
 
int  main()
{
    int i,n=11;
    int p;
    int s[12]={0,1,3,0,5,3,5,6,8,8,2,12},f[12]={0,4,5,6,7,8,9,10,11,12,13,14};
    bool A[12];
    //printf("输入节目数：\n");
    //scanf("%d",&n);
    /*printf("请依次输入节目的开始和结束时间\n");
 for(i=0;i<n;i++)
 {
 scanf("%d %d",&s[i],&f[i]);
 }*/
    p=GreedSelector(n,s,f,A);
    printf("安排的节目个数为:%d\n",p);
    printf("节目的选取情况为(0表示不选 1表示选取):\n");
    for(i=1;i<=n;i++)
        printf("%d ",A[i]);
    printf("\n");
    return 0;
}