Question

杭电ACM 2037 今年暑假不AC，求参考源码。

最好结构清晰一点，给点讲解

Answer 1

使用qsort快速排序：

#include <stdio.h>
#include <stdlib.h>

typedef struct show_time{
	int begin;
	int end;
}show_time;

show_time ti[100];

int cmp(const void *a, const void *b)
{
	return (*(show_time *)a).end > (*(show_time *)b).end ? 1 : -1;
}

int main(int argc, char const *argv[])
{
	int i, m, j, sum;

	while(scanf("%d", &m) != EOF)
	{
		if (0 == m)
		{
			break;
		}
		for (i = 0; i < m; ++i)
		{
			scanf("%d%d", &ti[i].begin, &ti[i].end);
		}

		qsort(ti, m, sizeof(ti[0]), cmp);

		j = 0;
		sum = 1;
		for (i = 1; i < m; ++i)
		{
			if (ti[i].begin >= ti[j].end)
			{
				j = i;
				sum++;
			}
		}
		printf("%d\n", sum);
	}
	return 0;
}

Answer 2

最简单的贪心问题，选择不相交的区间问题。《算法竞赛入门经典》153页。
#include <iostream>
using namespace std;
int main()
{
int a[100],b[100];
int n;
int s=0,e=0;
int cont=0;
while(cin>>n&&n!=0){
cont=0;
for(int i=0;i<n;i++)
cin>>a[i]>>b[i];
for(int i=0;i<n;i++)
for(int j=i;j<n;j++){
if(b[i]>b[j]) {
swap(b[i],b[j]);
swap(a[i],a[j]);
}
}
//取第一个
cont++;
s=a[0];
e=b[0];
for(int i=1;i<n;i++){
if(a[i]>=e) {
cont++;
e=b[i];
}
}
cout<<cont<<endl;
}
return 0;
}