问题描述

设有n个活动的集合e={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si

要求:给出问题的贪心算法,并编程实现。

问题分析

考虑到每个活动只能单独进行,且要活动越多越好,所以考虑使用贪心算法,使越早结束的活动排在前面,这样就保证了活动尽可能多。如果一个活动的开始在前一个活动结束时间之前,则去掉该活动,保证每个时刻只有一个活动在承办。

活动设置图(每一个小横线代表一个活动)

算法设计:

(1) 储存方式:采用结构体储存方式,结构内包含一个活动开始以及结束时间。

(2) 使用文件方式从外存读取数据,费时为线性时间O(n)

(3) 对结构体数组进行以按照每个活动结束时间进行快速排序,所用时间复杂度为O(nlogn)

(4) 构建一维结构数组,将结束时间靠前且不与之前活动时间重叠的活动加入到数组。这里需要一个for循环,所需是时间为线性,所以时间复杂复杂度为O(n)

(5) 最后打印出输出活动序列,以及最大的活动数量。所需时间为线性时间O(n) + O(1)

综上所述,本算法时间复杂度为O(n)

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef struct
{
double start;
double end;
double time;
}activity;
bool cmp(activity a ,activity b){
return a.end < b.end ;
}
int string_to_number(string s){
stringstream ss(s) ;
int a = 0 ;
ss >> a ;
return a ;
}
int main()
{

char buffer[250];
ifstream in("activity.txt");
int number = 0 ;
string s ;
getline(in,s);
number = string_to_number(s);
s.clear();
vector<activity> v(number);
for(int i = 0 ; i < number ; ++i ){
in.getline(buffer,20);
sscanf(buffer,"%lf%lf",&v[i].start,&v[i].end);
v[i].time = v[i].end - v[i].start;
}
sort(v.begin(),v.end(),cmp);
vector<activity> m ;
for(int i = 0 ; i < v.size() ; ++i){
m.push_back(v[i]);
if( i + 1 == v.size()) {break;}
for(int j = i+1 ; j < v.size() ; ++j){
if(v[j].start >= v[i].end) {i = j - 1 ;break;}
}
}
cout << m.size()<<endl;
for(int i = 0 ; i < m.size() ;++i){
printf("%lf %lf\n",m[i].start,m[i].end);
}
return 0;
}

谢谢访问