贪心-区间问题

区间选点和最大不相交区间数量

区间选点问题描述

问题描述

给定 N个闭区间 [a_i,b_j]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。

输入格式

第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 a_i,b_j，表示一个区间的两个端点。

输出格式

输出一个整数，表示所需的点的最小数量。

数据范围

1≤N≤$10^2$,−$10^9$≤ai≤bi≤$10^9$

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

问题分析

1. 将区间按右端点排序
2. 遍历区间，如果该区间中不包含最后选的那个点，则选取区间右端点。如果包含最后选的那个点，则跳过。
3. 输出所选点的个数。

最大不相交区间数量问题描述

问题描述

给定 N个闭区间 [a_i,b_i]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
输出可选取区间的最大数量。

输入格式

第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 a_i,b_i，表示一个区间的两个端点。

输出格式

输出一个整数，表示可选取区间的最大数量。

数据范围

1≤N≤10⁵,−10⁹≤a_i≤b_i≤10⁹

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

问题分析

1. 将区间按右端点排序
2. 遍历区间，如果该区间和上一个选的区间有重合，则跳过。如果和上一个选的区间没有重合，则选取该区间。
3. 输出所选区间的个数。

代码

上述两个问题的题意基本差不多，因此可以代码相同。

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n;
struct Range
{
    int l,r;
    bool operator<(const Range &W)const
    {
        return r<W.r; // 重载小于运算符，用于排序
    }
}Range[N];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>Range[i].l>>Range[i].r; // 输入每个区间的左右端点
    sort(Range,Range+n); // 对区间按照右端点从小到大排序
    int res=0,ed=-2e9; // 初始化结果为0，ed为一个较小的数
    for(int i=0;i<n;i++)
    {
        if(Range[i].l>ed)  // 如果当前区间的左端点大于ed
        {
            res++;
            ed=Range[i].r; // 更新ed为当前区间的右端点
        }
    }
    cout<<res<<endl;
    return 0;
}

区间分组

区间问题的描述

问题描述

给定 N个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。

输入格式

第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 a_i,b_i，表示一个区间的两个端点。

输出格式

输出一个整数，表示最小组数。

数据范围

1≤N≤10⁵,−10⁹≤a_i≤b_i≤10⁹

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

问题分析

1. 将区间按左端点排序。
2. 依次遍历区间，如果当前区间能放到之前的某个集合中，则把该区间放到该集合，如果当前不能放到任意一个之前的集合中，则新开一个集合，把当前区间放到新开的集合中。
3. 集合的数量就是答案。

关键步骤是第二步，如何判断当前区间能否放到之前的集合中。解决方法如下:
记录每个集合中保存的区间的最右侧端点，如果当前区间的左端点不和某个集合中保存的区间的最右侧端点相交，则当前区间不和该集合相交，能放到该集合中。
也就是，我们只需判断当前区间的左端点 是否和 右侧端点最小的那个集合是否相交即可。
为了快速找出右侧端点最小的那个集合，可以使用小根堆保存每个集合的右端点。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n;
struct Range
{
    int l,r;
    bool operator<(const Range &W)const 
    {
        return l<W.l;
    }
}Range[N];
int main()
{
    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++)
    {
    // 如果堆为空或者堆顶元素大于等于当前区间的左端点，将当前区间的右端点加入堆中
        if(heap.empty() || heap.top()>=Range[i].l) heap.push(Range[i].r);
        else
        {
            heap.pop(); // 否则弹出堆顶元素
            heap.push(Range[i].r); // 将当前区间的右端点加入堆中
        }
    }
    cout<<heap.size()<<endl; // 输出堆的大小，即不重叠区间的数量
    return 0;
}

区间覆盖

区间覆盖问题描述

问题描述

给定 N个闭区间 [a_i,b_i] 以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出 −1。

输入格式

第一行包含两个整数 s和 t，表示给定线段区间的两个端点。
第二行包含整数 N，表示给定区间数。
接下来 N 行，每行包含两个整数 a_i,b_i，表示一个区间的两个端点。

输出格式

输出一个整数，表示所需最少区间数。
如果无解，则输出 −1。

数据范围

1≤N≤10⁵,−10⁹≤a_i≤b_i≤10⁹,−10⁹≤s≤t≤10⁹
输入样例：

1 5
3
-1 3
2 4
3 5

输出样例：

2

问题分析

1. 将所有区间按照左端点从小到大进行排序
2. 从前往后枚举每个区间，在所有能覆盖start的区间中，选择右端点的最大区间，然后将start更新成右端点的最大值

代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int st,ed; // 定义起点和终点
int n; // 区间个数
struct Range
{
    int l,r; // 区间的左右端点
    bool operator<(const Range &W)const
    {
        return l<W.l; // 重载小于运算符，用于排序
    }
}Range[N];
int main()
{
    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; // 初始化结果为0
    bool sucess=false; // 初始化成功标志为false
    for(int i=0;i<n;i++)
    {
        int j=i,r=-2e9; // 初始化j为i，r为一个较小的数
        while(j<n && Range[j].l<=st) // 当j小于n且当前区间的左端点小于等于起点时
        {
            r=max(r,Range[j].r); // 更新r为当前区间的右端点和r中的最大值
            j++; // j加1
        }
        if(r<st) // 如果r小于起点
        {
            res=-1; // 结果设为-1
            break; // 跳出循环
        }
        res++; // 结果加1
        if(r>=ed) // 如果r大于等于终点
        {
            sucess=true; // 成功标志设为true
            break; // 跳出循环
        }
        st=r; // 更新起点为r
        i=j-1; // i更新为j-1
    }
    if(!sucess) res=-1; // 如果成功标志为false，结果设为-1
    cout<<res<<endl; // 输出结果
    return 0;
}