学步园

事先声明，我学习贪心算法之前只是理解了动态规划的装配线调度问题，其它的动态规划基础基本为零，我感觉很多问题都可以用贪心来解决，因此在这里总结一下我学习贪心算法的过程，很多东西是靠做题和死记硬背理解的，唉，为自己的智商着急啊！

我采用通过acm题的方式来分析一下我理解的贪心算法！

题目描述：
又到毕业季，很多大公司来学校招聘，招聘会分散在不同时间段，小明想知道自己最多能完整的参加多少个招聘会(参加一个招聘会的时候不能中断或离开)。
输入：
第一行n，有n个招聘会，接下来n行每行两个整数表示起止时间，由从招聘会第一天0点开始的小时数表示。
n <= 1000 。
输出：
最多参加的招聘会个数。
样例输入：
3
9 10
10 20
8 15
样例输出：
2

活动选择问题

这个问题是对几个相互竞争的招聘会活动进行调度，它们都要求以独占的方式使用某一公共资源（小明）。调度的目标是找出一个最大的相互兼容的活动集合。这里是有一个需要使用某一资源（小明）的n个活动组成的集合S={a1,a2,...,an}.该资源一次只能被一个活动占用。每个活动ai有开始时间si和结束时间fi，且0<=si<fi<无穷。一旦被选择后，活动ai就占据了区间[si,fi].如果区间[si,fi]和[sj,fj]互不重叠，称活动ai和aj是兼容的。活动选择问题就是要选择出一个由互相兼容的问题组成的最大子集合。

将所有的活动按照结束时间升序排列

i	1	2	3
si	9	8	10
fi	10	15	20

定理

fm=min{fk:ak属于Sij}

那么，

1）活动am在Sij的某最大兼容活动子集中被使用

2）子问题Sim为空，所以选择am将使子问题Smj为唯一可能非空的子问题

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct join
{
    int begin;
    int end;
};
 
int compare(const void *a, const void *b);
 
int main()
{
    int i, n, k;
    struct join joins[1001], temp[1001];
 
    while(scanf("%d", &n) != EOF)
    {
        for(i = 0; i < n; i ++)
        {
            scanf("%d %d", &joins[i].begin, &joins[i].end);
        }
         
        qsort(joins, n, sizeof(joins[0]), compare);
 
        k = 0;
        temp[k] = joins[0];
        for(i = 1; i < n; i ++)
        {
            if(joins[i].begin >= temp[k].end)
                temp[++ k] = joins[i];
        }
        printf("%d\n", k + 1);
    }
     
    return 0;
}
 
int compare(const void *a, const void *b)
{
    const struct join *p = a;
    const struct join *q = b;
 
    return p->end - q->end;
}
/**************************************************************
    Problem: 1463
    User: wangzhengyi
    Language: C
    Result: Accepted
    Time:10 ms
    Memory:904 kb
****************************************************************/