一：区间选点（终点排序）

原理：

选最少的点，在所有的闭区间中

区间问题思考排序：

• 左端点排序
• 右端点排序
• 双关键字排序,现在不理解？？？

每次挑选当前最好的，贪心问题解决必须是单峰，多峰可能挑选的局部最优解。

下面这句话是精髓，排序以后，找到最大不相交，两个区间不相交，就至少需要两个点，如果相交，直接pass，结合代码

代码（按照区间终点）：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W)const //sort排序选择
    {
        return r < W.r;
    }
} range[N];
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> range[i].l >> range[i].r;
    sort(range, range + n); // 结构体数组排序方式，死记硬背
    int res = 0;
    int end = -0x3f3f3f3f;
    for (int i = 0; i < n; i++)
        if (end < range[i].l) // 只要是区间不相交，点就需要加1，可以的话直接跳过
        {
            res ++;
            end = range[i].r;
        }
    cout << res << endl;
    return 0;
}

代码（按照区间起点）：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct Range
{
    int  l,r;
    bool operator <(const Range &W)const
    {
        return l<W.l;
    }
}range[N];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        range[i]={l,r};
    }
    sort(range,range+n);
    int res=0,st=-2e9;
    for(int i=0;i<n;i++)
    {
        if(st<range[i].l)
        {
            res++;
            st=range[i].r;
        }
        else // 没有这里是错误的，对特殊情况的处理
        {
            st=min(st,range[i].r);
        }
    }
    printf("%d\n",res);
    return 0;
}

上面的else没有处理就会出现这种错误，导致起点出错，加了else就会发现，取了9作为其实点，这样以为就是9可以选取为两个区间的公共点，也算是起点了。

别人总结的：

二：最大不想交区间的数量

代码同上

三：区间分组(左端点排序)

存在这样的组，随便挑一个放进去

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
const int N = 1e5 + 10;

struct Range{
    int l, r;
    bool operator< (const Range &W) const {
        return l < W.l;
    }
} range[N];

int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> range[i].l >> range[i].r;
    sort(range, range + n);
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 0; i < n; i++)
    {
        auto k = range[i];
        if (heap.empty() || heap.top() >= k.l) heap.push(k.r);
        else
        {
            heap.pop();
            heap.push(k.r);
        }
    }
    cout << heap.size() << endl;
    return 0;
}

四：区间覆盖（左端点排序）

核心：选择能覆盖左端点，并且右端点尽量靠右。注意不是最长的，因为本质目的就是覆盖。

• 逻辑一定得弄清楚，你要找的是区间覆盖左端点，最终右端点还要大于目标区间的右端点，这就是两个检验点，程序的逻辑自然要体现。 ```cpp

  include

  include

using namespace std;

const int N = 1e5 + 10;

struct Range { int l, r; bool operator< (const Range &W) const { return l < W.l; } } range[N];

int main() { ios::sync_with_stdio(false); int n, st, ed; cin >> st >> ed; cin >> n; for (int i = 0; i < n; i++) cin >> range[i].l >> range[i].r; sort(range, range + n); int res = 0; bool flag = false; // 必须有 for (int i = 0; i < n; i++) { int j = i; // 双指针算法的核心 int r = -0x3f3f3f3f; // 不断合并区间的最大值 while (j < n && range[j].l <= st) // 找到覆盖st的点，并且区间重点最靠右的的区间 { r = max(r, range[j].r); j ++; } if (r < st) // 区间最左端点可能都不覆盖st { res= -1; break; } res++; // 计数区间的个数 if (r >= ed) // 上面条件满足，有可能区间右边的点不满足，这也是flag存在的意义 { flag = true; break; } st = r; // 每轮更新st i = j - 1; // 每次循环i都自加1，j在while++已经满足，但是因为i还要++，所以提前-1 } if (!flag) res = -1; cout << res << endl; return 0; } ```