现将举行一个餐会，让访客事先填写到达时间与离开时间，为了掌握座位的数目，必须先估计不同时间的最大访客数。

解法：

将来访时间与离开时间分开处理，假设访客i的来访时间为x[i]，离开时间为y[i].

在籽料输入完毕之后，将x[i]与y[i]分别进行排序，只要先计算某时之前来了多少访客，然后再减去某时之前离开的访客，即可。

#include <stdio.h>
#include <stdlib.h>
#define MAX 100
#define SWAP(x,y) {int t; t = x; x = y; y = t;}

int partition(int[], int, int);
void quicksort(int[], int, int);
int maxguest(int[], int[], int, int);
int main(void)
{
	int x[MAX] = {0};
	int y[MAX] = {0};
	int time = 0;
	int count = 0;
	printf("\n输入来访与离开时间：时间（0~24）");
	printf("\n范例：10 15");
	printf("\n输入-1 -1结束");
	while(count < MAX)
	{
		printf("\n>>");
		scanf("%d %d", &x[count], &y[count]);
		if(x[count] < 0)
		{
			break;
		}
		count++;
	}
	if(count >= MAX)
	{
		printf("\n超出最大访客数(%d)", MAX);
		count--;
	}
	quicksort(x, 0, count);
	quicksort(y, 0, count);
	while(time < 25)
	{
		printf("\n%d时的最大访客数:%d", time, maxguest(x, y, count, time));
		time++;
	}
	printf("\n");
	return 0;
}

int maxguest(int x[], int y[], int count, int time)
{
	int i, num = 0;
	for(i = 0; i <= count; i++)
	{
		if(time > x[i])
		{
			num++;
		}
		if(time > y[i])
		{
			num--;
		}
	}
	return num;
}

int partition(int number[], int left, int right)
{
	int i, j, s;
	s = number[right];
	i = left - 1;
	for(j = left; j < right; j++)
	{
		if(number[j] <= s)
		{
			i++;
			SWAP(number[i], number[j]);
		}
	}
	SWAP(number[i+1], number[right]);
	return i+1;
}

void quicksort(int number[], int left, int right)
{
	int q;
	if(left < right)
	{
		q = partition(number, left, right);
		quicksort(number, left, q-1);
		quicksort(number, q+1, right);
	}
}

转载请注明：于哲的博客 » 最大访客数