贪心算法练习——活动安排
一．（1）实验名称：时间复杂度为O(n2)输出最少会场安排个数。
（2）算法思想：开始时间输入s数组，结束时间时输入f数组，将标记置为0，然后按结束时间对s数组和f数组排序，j记录上一个活动的结束时间，用循环往后找第一个大于结束时间的开始时间，找到后将标记置为1，每一次循环结束后让计数器加1，即安排了一个会场，直至所有的时间都被标记完，此时所有活动都已经安排完毕。
（3）代码如下：
#include <stdio.h>
#define N 5
typedef struct start
{
int stime;
int flag;
}s[N];
typedef struct fininal
{
int ftime;
int targe;
}f[N];
int Activity_Arrangement(start s[], fininal f[])
{
int i, count = 1, t = 0, j, k;
while (count < N)
{
for (i = 0; i < N; i++)
{
if (s[i].flag == 0)
{
j = i;
k = j;
break;
}
}
for (i = 0; i < N; i++)
{
if (s[i].flag == 0 && f[j].ftime < s[i].stime)
{
count++;
s[i].flag = 1;
f[j].targe = 1;
j = i;
}
}
if (j == k)
count++;
t++;
}
return t;
}
void sort(start s[], fininal f[])
{
int i, j;
start m;
fininal n;
for (i = 0; i < N - 1; i++)
{
for (j = i + 1; j < N; j++)
{
if (f[i].ftime > f[j].ftime)
{
n = f[i];
f[i] = f[j];
f[j] = n;
m = s[i];
s[i] = s[j];
s[j] = m;
}
}
}
}
int main(void)
{
int i;
start s[N];
fininal f[N];
for (i = 0; i < N; i++)
{
scanf("%d%d", &s[i].stime, &f[i].ftime);
s[i].flag = 0;
f[i].targe = 1;
}
sort(s, f);
printf("%d\n", Activity_Arrangement(s, f));
return 0;
}
二．（1）实验名称：时间复杂度为O(n)输出最少会场个数。
（2）算法思想：将开始时间和结束时间置于同一数组，并对数组升序排序，开始时间标记为0，结束时间标记为1，对数组进行一次遍历，遇到0计数器加1，遇到1计数器减1，返回这个过程中count的最大值，即为会场安排的最小个数。如果一个活动还没结束下一个活动已经开始，说明两个活动不能安排在同一会场，则存在冲突，冲突的个数即为会场最小个数。
（3）代码如下：
#include <stdio.h>
#define N 10
typedef struct Activity
{
int time;
int flag;
}act[N];
int Activity_Arrangement(Activity s[])
{
int i, count = 0, max = 0;
for (i = 0; i < N; i++)
{
if (s[i].flag == 0)
{
count++;
if (max < count)
max = count;
}
else
count--;
}
return max;
}
void sort(Activity act[])
{
int i, j;
Activity k;
for (i = 1; i < N - 1; i++)
{
for (j = i + 1; j < N; j++)
{
if (act[i].time > act[j].time)
{
k = act[j];
act[j] = act[i];
act[i] = k;
}
}
}
}
int main(void)
{
int i, j = N / 2;
Activity act[N];
for (i = 0; i < N / 2; i++)
{
scanf("%d%d", &act[i].time, &act[j].time);
act[i].flag = 0;
act[j].flag = 1;
j++;
}
sort(act);
printf("%d\n", Activity_Arrangement(act));
return 0;
}
