贪心算法是一种解决优化问题的算法。其基本思想是将整个问题分解成一系列子问题,并为每个子问题找到最优解决方案,最终通过组合子问题的解来得到整个问题的解。
本题:1.先对结束时间进行排序并将之对应开始时间的储存位置进行对应变更;2.以最先结束的时间为起点向后寻找匹配的开始时间并将sum++(sum初始值为1)
#include<stdio.h>
#include<stdlib.h>
void main()
{
int n, i, * tis, * tie,j,temp,sum;
while (~scanf_s("%d", &n) && n != 0)
{
sum = 1;
tie = (int*)malloc(n * sizeof(int));
tis = (int*)malloc(n * sizeof(int));
for (i = 0; i < n; i++)
scanf_s("%d %d", &tis[i], &tie[i]);
for (i = 0; i < n; i++)
for (j = 1; j < n-i; j++)
if (tie[j - 1] > tie[j])
{
temp = tie[j - 1], tie[j - 1] = tie[j], tie[j] = temp;
temp = tis[j - 1], tis[j - 1] = tis[j], tis[j] = temp;
}
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if (tie[i] <= tis[j])
{
sum++; i = j;
}
printf("%d\n", sum);
}
}