思路：将所有区间先按左端点从大到小排序，再按右端点从小到大排序，从第一个区间开始，记录当前区间的左端点位置lateX，遍历区间数组，如果当前区间的右端点小于lateX, 说明当前区间与上一个区间不相交，将计数器加一，更新lateX为当前区间左端点的值。

模板代码：

 1 // 区间贪心
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 110;
 8 
 9 // 定义一个结构体存储所有区间
10 struct Inteval{
11     int x, y;        // 开区间左右端点
12 }I[maxn];
13 
14 // 比较函数
15 bool cmp(Inteval a, Inteval b)
16 {
17     if (a.x != b.x)
18         return a.x > b.x;            // 先按左端点从大到小排序
19     else 
20         return a.y < b.y;            // 再按右端点从小到大排序
21 }
22 
23 int main()
24 {
25     freopen("in.txt", "r", stdin);
26     int n;
27      // 读取数据
28     while (scanf("%d", &n), n != 0)
29     {
30         for (int i = 0; i < n; i++)
31         {
32             scanf("%d %d", &I[i].x, &I[i].y);
33         }
34 
35         // 排序
36         sort(I, I + n, cmp);
37             
38         // 统计不相交区间的个数
39         // ant存储个数， lateX存储最近的X
40         int ant = 1, lateX = I[0].x;
41 
42         // 遍历这个数组
43         for (int i = 1; i < n; i++)
44         {
45             if (I[i].y <= lateX)
46             {
47                 ant++;
48                 lateX = I[i].x;            // 更新lateX的值
49             }
50         }
51         printf("%d\n", ant);
52     }
53 
54     fclose(stdin);
55     return 0;
56 }

应用区间贪心算法的另一种题目形式：

 

 这题的算法思路其实和上题是一样，大区间包含小区间只考虑小区间的个数，因为在小区间中一定存在于大区间中；区间相交只需选取其中一个区间，所以也变成了求最大不相交区间的个数的问题，但是因为这题的区间是闭区间，所以上面的 I[i].y <= lateX 要改成I[i].y < lateX 。

 

 本博客内容大部分引用 胡凡的《算法笔记》