greedy.c

来自「自己做的常用库和实现的数据结构。public domain.」· C语言 代码 · 共 41 行

/* Demo of simple greedy algorithm. 
 *
 * Written by Cyril Hu ([e-mail]), public domain.
 */

#include<stdio.h>
#include<stdlib.h>
#define MAX 9

typedef struct ab {
	int a;
	int b;
} AB;
AB x[MAX]={{10,13},{8,13},{10,12},{2,8},{1,6},{5,13},{5,8},{12,16},{7,8}};

int main(void)
{
	int i,t,j;
	
	/* selective sort, ascending, in keyword x[i].b */
	for(i=0; i<MAX-1; i++) {
		for(j=i,t=i+1; t<MAX; t++) 
			if(x[j].b > x[t].b)
				j = t;
		t = x[j].a; x[j].a = x[i].a; x[i].a = t;
		t = x[j].b; x[j].b = x[i].b; x[i].b = t;
	}

	/* pick as much field as possible */
	for(i=0; i<MAX; i++) {
		printf("%d %d\t", x[i].a, x[i].b);
		for(j=i+1; j<MAX; j++) {
			if(x[i].b <= x[j].a)
				break;
		}
		i = j-1;
	}

	return EXIT_SUCCESS;
}