《贪心练习题-最少需要几个数》，您将学到贪心的本质是什么，贪心的常规解法就是利用人类自然智慧去思考，往往利用比较器排序或堆来解题。

一、题目

给定区间的范围[xi,yi] ， xi <= yi ， 且都是正整数，找出一个坐标集合Set ，Set中有若干个数字，Set要和每个给定的区间有交集，求Set中最少需要的几个数。

比如给定区间：[5,8]、[1,7]、[2,4]、[1,9]，Set最小可以是：{2,6} 或者 {2,5} 或者 {4,5}等满足规则的答案。

二、分析

按照每个序列的xi值从小到大排序，每个序列可以生成2个事件，一个开头事件和一个结尾事件，每个事件包含3个属性，事件以谁开头，事件发生时是开头还是结尾，事件以谁结尾。

比如有4个系列分别是[5,8]、[1,7]、[2,4]、[1,9]，总共生成8个事件

按照序列的xi值从小到大排序，生成事件结果如下：

(1,开头,7)，(1,开头,9)，(2,开头,4)，(4,结尾)，(5,开头,8)，(7,结尾)，(8,结尾)，(9,结尾)

贪心利用人类自然智慧，最常见的做法就是排序（比较器），给定的区间是乱序的，需要以某种机制来排序，把序列区间转化为事件机制，按照假设的事件机制来做。

int[][] ranges代表序列们，二维数组，总共有N个数列，每个序列表示{xi,yi}

先把所有的序列按照规定的事件进行转化，规定如下：

• events[i] = {a, b, c}
• a == 0, 表示这是一个区间的开始事件，这个区间结束位置是b
• a == 1, 表示这是一个区间的结束事件，b的值没有意义
• c表示这个事件的时间点，不管是开始事件还是结束事件，都会有c这个值

所有序列按照xi值从小到大排序，也就是按照时间的c值进行从小到大排序，定义一个容器，如果是开始事件，则添加进容器，如果是结束事件，则需要判断容器是否存在该值，如果存在，则需要此数，必定是之前走过的所有序列中都包含的数字，因为是按照从小到大排序的，这也就是体现贪心的地方。

三、实现

public static int minSet(int[][] ranges) {
    int n = ranges.length;
    int[][] events = new int[n << 1][3];
    for (int i = 0; i < n; i++) {
        // [3, 7]
        // (0,7,3)
        // (1,X,7)
        events[i][0] = 0;
        events[i][1] = ranges[i][1];
        events[i][2] = ranges[i][0];
        events[i + n][0] = 1;
        events[i + n][2] = ranges[i][1];
    }
    Arrays.sort(events, (a, b) -> a[2] - b[2]);
    // 容器
    HashSet<Integer> tmp = new HashSet<>();
    int ans = 0;
    for (int[] event : events) {
        if (event[0] == 0) {
            tmp.add(event[1]);
        } else {
            if (tmp.contains(event[2])) {
                ans++;
                tmp.clear();
            }
        }
    }
    return ans;
}