贪心算法中不想交区间问题：题目
解题思路：定义两个变量，一个记为结束时间，一个记为区间数。将结束时间排序，若相同，就将开始时间从大到小排序；若不同，就将结束时间按从小到大排序。这样第一个区间是确定的，再比较下一个区间的开始时间与第一个区间结束时间的大小，大于则加一。再将结束时间改变即可，继续循环。
#include <stdio.h> #include <algorithm> using namespace std ; typedef struct time { int s,f; }time; bool cmp(time a,time b) { if(a.f == b.f) return a.s > b.s; else return a.f < b.f; } int main() { int n; while(scanf("%d",&n) != EOF) { time arr[1005]; for(int i = 0;i < n;i++) scanf("%d %d",&arr[i].s,&arr[i].f); sort(arr,arr + n,cmp); int ans,last; ans = 1; last = arr[0].f; for(int j = 0;j < n;j++) { if(last <= arr[j].s) { ans += 1; last = arr[j].f;//注意改变结束时间！ } } printf("%d",ans); } return 0; }
再将结构体排序举两个例子
1.摘苹果
Description
小明家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。苹果成熟的时候，小明就会跑去摘苹果。小明有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。现在已知10个苹果到地面的高度，以及小明把手伸直的时候能够达到的最大高度，请帮小明算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。
Input
第一行输入N（0＜N＜100）表示测试数据组数，接下来每组测试输入包括两行数据。
第一行包含10个100到200之间（包括100和200）的整数（以厘米为单位）分别表示10个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。
第二行只包括一个100到120之间（包含100和120）的整数（以厘米为单位），表示小明把手伸直的时候能够达到的最大高度。
Output
输出包括一行，这一行只包含一个整数，表示小明能够摘到的苹果的数目。 Sample Input
1
100 200 150 140 129 134 167 198 200 111
110
Sample Output
5
#include <stdio.h> #include <algorithm> using namespace std ; bool cmp(char a,char b) { return a < b;//当从小到大排序时可以不用cmp函数 } int main() { int N; int arr[12]; while(scanf("%d",&N) != EOF) { for(int k = 0;k < 2;k++) { for(int i = 0;i < 10;i++) { scanf("%d ",&arr[i]); } int m,h; int sum = 0; scanf("%d",&m); h = m + 30; sort(arr,arr + 10,cmp);//sort(数组名，数组名+里面数的个数，cmp) for(int j = 0;j < 10;++j) { if(arr[j] <= h) sum += 1; } printf("%d\n",sum); } } return 0; }
2.ASCII码排序
Description
输入三个字符（可以重复）后，按各字符的ASCII码从小到大的顺序输出这三个字符。
Input
第一行输入一个数N,表示有N组测试数据。后面的N行输入多组数据，每组输入数据都是占一行，有三个字符组成，之间无空格。
Output
对于每组输入数据，输出一行，字符中间用一个空格分开。
Sample Input
2
qwe
asd
Sample Output
e q w
a d s
#include <stdio.h> #include <algorithm> using namespace std; bool cmp(char a,char b) { return a < b; } int main() { int N; scanf("%d",&N); while(N--) { char arr[5];//char类型！！ scanf("%s",arr);//将整个字符串输进去 sort(arr,arr + 3,cmp); printf("%c %c %c\n",arr[0],arr[1],arr[2]);//将每个字符输出来，省的考虑空格问题…… } return 0; }
