区间贪心¶

固定长度区间选最多的不重叠区间个数¶

n个区间，选择尽量多个区间，使得这些区间两两不相交。（实际上就是抽象版的区间调度问题）

核心思路：

右端点排序（<），再从左到右遇到不相交的就选

核心代码：

vector<pair<int, int>> job(n);
int res = 0, t = 0;
sort(job.begin(), job.end());
for (int i = 0; i < n; ++i) {
    if (t < job[i].second) {
        ++res;
        t = job[i].first;
    }
}
cout << res << endl;

在构建pair的时候使用了一个小技巧，因为目标是让先结束的任务排在前面，所以键选择结束时间，而值选择任务开始时间。用变量t来代表上一个选取的任务的结束时间，如果遍历数组job，发现下一个对象的开始时间大于t，则说明这个任务可选，并且一定是后面所有可选任务里面最先结束的（因为之前排序的原因）

典型题目：

《挑战程序设计竞赛》2.2.2 区间问题 => 固定长度区间选最多的不重叠区间个数

选点覆盖坐标值¶

n个坐标值，每个点左右可以覆盖一定的范围，选择尽量少的点覆盖所有的坐标值。这种题目也可能伪装成区间覆盖问题，比如：

设x1 , x2,... , xn是实直线上的n个点。用固定长度的闭区间覆盖这n个点，至少需要多少个这样的固定长度闭区间?设计解此问题的有效算法，并证明算法的正确性。

核心思路：

对于输入的坐标值序列先排序，然后找第一个没有被标记的点，以此开始，去寻找最后一个小于当前坐标+覆盖范围的点，这个点作为标记点，然后找下一个不在覆盖范围内的点，作为新的起点，循环直到序列结束。

核心代码：

sort(sequence.begin(), sequence.begin() + n);
int mark()
{
    int cnt = 0;
    int pos = 0;
    while (true) {
        int target = sequence[pos] + range; //下面去寻找最后一个不大于目标值的数
        while (pos < n && sequence[pos] <= target) {++pos;}
        ++cnt;
        if (pos >= n) break;
        pos = pos - 1;
        target = sequence[pos] + range; //寻找第一个大于目标值的数
        while (pos < n && sequence[pos] <= target) {++pos;}
        if (pos >= n) break;
    }

    return cnt;
}

典型题目：

POJ 3069 Saruman's Army

最少区间覆盖¶

数轴上有n个闭区间[ai,bi]，选择尽量少的区间覆盖一条指定的线段[s,t]

左端点排序（<）兼顾右端点（<），每次选择从当前起点能覆盖到的最长的区间

//POJ 2376 Cleaning Shifts
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 0x0ffffff; 

struct Node
{
    int left, right;
    bool operator<(const Node & obj) const
    {
        return left < obj.left;
    }
};

int n = 25000, t;
vector<Node> sequence(n);

int cowNum()
{
    sort(sequence.begin(), sequence.begin() + n);

    int cnt = 0; //计数需要多少头牛
    //pos是下一轮搜索的下标，end是上一轮的最右边界，start是辅助去搜索下一个点
    int pos = 0, start = 0, end = 0;
    while (pos < n) {
        //之所以+1是因为需要覆盖的是整数值
        start = end + 1;
        for (int i = pos; i < n; ++i) {
            if (sequence[i].left <= start) {
                if (sequence[i].right > end) end = sequence[i].right;
                if (end >= t) {++cnt; return cnt;}
            }
            else {
                //更新pos
                pos = i;
                break;
            }
        }
        //没有找到一个合适的区间
        if (end < start) return -1;
        ++cnt;
    }
    //搜索结束仍没有return，代表全部区间都无法覆盖，所以无解
    return -1;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> t;
    for (int i = 0; i < n; ++i) {
        cin >> sequence[i].left >> sequence[i].right;
    }    
    cout << cowNum() << endl;

    return 0;
}

典型题目：

区间选点¶

数轴上有N个闭区间[Ai, Bi]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。

核心算法：

int solve()
{
    sort(sequence.begin(), sequence.begin() + n);

    int cnt = 1;
    double range = sequence[0].right;
    for (int i = 1; i < n; ++i) {
        if (sequence[i].left <= range) range = min(range, sequence[i].right);
        else {
            ++cnt;
            range = sequence[i].right;
        }
    }

    return cnt;
}

典型题目：

POJ-1328 Radar Installation(贪心，区间选点)

区间划分¶

时间轴上有n个开区间(ai, bi)，把这些区间至少划分成多少个集合，使得每个集合中的区间两两没有公共点。因为是开区间，所以(1, 2)和(2,3)可在一个集合中

核心思路：

仍然是读取区间的左右端点，但是排序上会有所不同，左端是升序排列，如果左端点相同，那么右端点按降序排列，这样做的原因是，考虑一个区间，它是否可以加入到某个集合，取决于当前区间的左端点和所有集合的最右端点的大小比较，如果当前区间左端点大于集合的右端点，那么肯定选两者最接近的加入，这样为更多的区间加入留下位置。发现只和集合的右端点有关，那么考虑如何记录集合的最右端点，可以利用一个向量去保存。那么刚才的右端点降序排列就起了作用，只要顺序比较，只要发现一个集合的右端点小于当前区间的左端点，那么就立刻加入，两者之间的差值一定是所有可以加入的集合里面最小的。

//LeetCode 253.Merting Rooms II
class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        sort(intervals.begin(), intervals.end(), [](vector<int> & a, vector<int> & b){return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);});

        int cnt = 0;
        //使用小根堆
        priority_queue<int, vector<int>, greater<int>> pq;
        int n = intervals.size();
        for (int i = 0; i < n; ++i) {
            if (pq.empty()) { //会议室为空
                pq.push(intervals[i][1]);
                ++cnt;
            }
            else {
                int num = pq.top(); pq.pop();
                //可以安排进去
                if (num <= intervals[i][0]) {
                    pq.push(intervals[i][1]);
                }
                else {
                    ++cnt;
                    pq.push(num);
                    pq.push(intervals[i][1]);
                }
            }
        }

        return cnt;
    }
};

典型例题：

POJ 3190 Stall Reservations
LeetCode 253.Merting Rooms II

另外在一篇博客上找到的问题：

题目描述

时间限制: 1 Sec 内存限制: 128 MB 时间轴上有n个开区间(ai, bi)，把这些区间至少划分成多少个集合，使得每个集合中的区间两两没有公共点。因为是开区间，所以(1, 2)和(2,3)可在一个集合中

输入

第1行：一个整数N(1 <= N <=10^5) 接下来N行，每行2个整数Ai，Bi(0<= Ai < Bi < 10^7)

输出

第1行：1个整数，需要划分成的最少集合数。

样例输入

样例输出

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 0x0ffffff;

struct Node
{
    int left, right;
    //左端点升序，右端点降序
    bool operator<(const Node & n) const
    {
        return (left < n.left || (left == n.left && right > n.right));
    }
};

int n = 1001;

vector<Node> sequence(n); //记录所有区间的左右端点
vector<int> record(n); //记录各个集合的最右端点

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> sequence[i].left >> sequence[i].right;
    sort(sequence.begin(), sequence.begin() + n);

    int cnt = 0;
    record[0] = sequence[0].right;

    for (int i = 1; i < n; ++i) {
        bool havePos = false; //判断已知的集合是否可以加入当前区间
        //遍历集合的右端点
        for (int j = 0; j <= cnt; ++j) {
            if (sequence[i].left >= record[j]) {
                record[j] = sequence[i].right;
                havePos = true;
                break;
            }
        }
        //遍历完发现没有集合可以加入，那么需要增加一个集合
        if (!havePos) {
            ++cnt;
            record[cnt] = sequence[i].right;
        }
    }

    cout << (cnt + 1) << endl; 

    return 0;
}

但是注意，这种方法在处理POJ 3190的时候会超时，因为考虑特殊情况，如果每个区间一个集合，那么这就是 $O(n^2)$ 的算法，所以应该考虑用优先级队列来进行优化。

上面的算法之所以会超时，是因为对于整个过程分析的不够细致，因为考虑如果每一次加入新的一头奶牛就要全部对比，这样很耗时间，是否可以利用数据结构来优化这个过程？

首先肯定是要对输入的序列进行排序，那么目前见过的排序技巧有区间调度里面的右端点排序，初始排序左端点升序，左端点相同，右端点升序。

利用优先级队列的优化，每次取出最早结束的时间，如果最早结束的时间小于序列的开始时间，那么就可以加入围栏，否则就需要新开一个围栏。这样就只需要去进行一次比较，我们需要对这个过程进行证明。

首先考虑队列为空和不为空的两种情形。队列为空的情形比较好处理，不为空的情形需要细节分析。

首先队列的优先级是根据结束时间来确定的，结束的时间越早，优先级就越高。那么需要证明为什么只需要去比较一次。考虑最早结束的时间，如果其小于序列的开始时间，那么第二早结束的时间虽然也有可能小于序列开始的时间，所以会不会存在一种情况，就是最早结束的时间和序列开始的时间内可以插入一个新的序列点。答案是不会的，因为排序是按照序列开始时间升序排列的，当前序列的后面的点的开始时间是不会比当前的开始时间早的。那么此时去更新这个结束时间即可（删掉队列原有的点，加入一个新的点）。

如果最早结束的时间大于等于序列的开始时间，因为队列是按照最早结束的时间来确定优先级的，那么意味着队列里的其他的结束时间肯定也比序列的开始时间要大，意味着已经没有围栏合适了，那么就需要去增加一个围栏。

题目特殊的地方是需要“输出路径”，也就是需要按照输入的顺序去输出每头牛被分配的围栏号，所以需要去记录初始的输入顺序和用一个数组record 去记录每头牛被分配的围栏号。

典型题目：