题目描述

An integer interval [a, b] (for integers a < b) is a set of all consecutive integers from a to b, including a and b.

Find the minimum size of a set S such that for every integer interval A in intervals, the intersection of S with A has size at least 2.

Example 1:

Input: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
Output: 3
Explanation:
Consider the set S = {2, 3, 4}.  For each interval, there are at least 2 elements from S in the interval.
Also, there isn't a smaller size set that fulfills the above condition.
Thus, we output the size of this set, which is 3.

Example 2:

Input: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]
Output: 5
Explanation:
An example of a minimum sized set is {1, 2, 3, 4, 5}.

Note:

1. intervals will have length in range [1, 3000].
2. intervals[i] will have length 2, representing some integer interval.
3. intervals[i][j] will be an integer in [0, 10^8].

题意：一个整数区间 [a, b] ( a < b ) 代表着从 a 到 b 的所有连续整数，包括a 和b。给你一组整数区间intervals，请找到一个最小的集合 S，使得 S 里的元素与区间intervals中的每一个整数区间都至少有2个元素相交。输出这个最小集合S的大小。

算法1

(贪心/排序) $O(nlogn)$

题解：首先明确我们找的S是一个点集合不一定是一个线段。接下来我们考虑如何贪心，基本上所有的线段题目都是按照左端点或者右端点排序然后遍历处理，这题也不例外。我们先按照右端点进行排序，这时候我们可以发现我们应该尽可能的把这条线段的右端点加入到集合中，这是因为后续的线段的右端点大于当前线段右端点，如果我们选择一个当前线段前面位置上的点能被后面的线段利用，那么当前线段的右端点也一定能被后面的线段利用，即不会得到更坏的结果。

基于上述思想，我们也知道我们集合S中的点也是按照升序加入进来的，那么接下来我们考虑已经加入的点集合S共cnt个点中最后两个点S[cnt - 1],S[cnt]和新线段A的关系：

如果A[0] > S[cnt],说明当前已经选择的点必然不能不被A利用，所以我们要将A中最后两个点加入集合S中。

如果A[0] <= S[cnt - 1]，那么说明S[cnt - 1],S[cnt]都在线段A中，我们无需加入额外的点。

否则的话S[cnt - 1] < A[0] <= S[cnt]，这时候S[cnt]在线段A中，我们只需要将A中最后一个端点加入进来就可以了。

这里我们还需要考虑的一点在排序的时候，如果两个区间的右端点相同了，我们需要怎么排序呢？我们先处理较短的那个区间，这是因为如果我们先处理较长的区间会出现如下的问题：假设已经加入的最后两个点为2，5，A1 = [6,10],A[2] = [4,10]。如果我们先处理A2的话按照上述规则，我们会加入一个点10，这时候再处理A1，因为现在集合中是2，5，10，我们又会加入一个10，这就会造成错误。如果我们先处理A1加入了10之后，A2不会加入任何点。

    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),[](const vector<int> &a,const vector<int> &b)
             {
                 return a[1] == b[1]? a[0] > b[0] : a[1] < b[1];
             });
        vector<int> dots = {-1};
        int n = intervals.size(),cnt = 0;
        for(int i = 0 ; i < n ; i ++)
        {
            if(intervals[i][0] > dots[cnt])
            {
                dots.push_back(intervals[i][1] - 1);
                dots.push_back(intervals[i][1]);
                cnt += 2;
            }else if(intervals[i][0] <= dots[cnt - 1])
            {
                continue;
            }
            else
            {
                dots.push_back(intervals[i][1]);
                cnt += 1;
            }
        }
        return cnt;
    }