区间合并

按左端点排序,模拟

https://www.acwing.com/problem/content/805/

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct node
{
    int l,r;
}record[N];
int cmp(node a,node b)
{
    return a.l<b.l;//按左端点排序
}
int n,l,r;
int main()
{   ios::sync_with_stdio(false);
cin>>n;
int ans=1;//初始化，肯定有一个区间
for(int i=0;i<n;i++)
    cin>>record[i].l>>record[i].r;
sort(record,record+n,cmp);
int end=record[0].r;
for(int i=1;i<n;i++)
{
   if(record[i].l>end)  //下一个区间的左端点大于右端点,不能进行合并
   {
       ans++; // 答案累加
       end=record[i].r; //将右端点更新
   }
   else if(record[i].r>end)  //下一个区间的左端点小于上一个区间的右端点,下一个区间的右端点大于上一个区间的右端点
   //可以进行合并
    end=record[i].r;  //将右端点更新
}
cout<<ans<<endl;
    return 0;
}

区间覆盖

左端点排序

贪心方法:每次选当前区间左端点能够与上一个区间连接上的最靠后的右端点,肯定越长越好

https://www.acwing.com/problem/content/909/

https://www.acwing.com/problem/content/description/4424/

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int s, t;
int n;
#define l first
#define r second
typedef pair<int, int> pii;
pii a[N];
int ans;
int main()
{
    cin >> s >> t;
    cin >> n;
    bool ok = false;
    for (int i = 0; i < n; i++)
        cin >> a[i].l >> a[i].r;
    sort(a, a + n); //左端点排序
    for (int i = 0; i < n; i++)
    {
        int j = i;
        int end = -0x3f3f3f3f;
        while (j < n && a[j].l <= s) //找到满足条件的左端点,右端点最大的区间,选它
        {
            end = max(end, a[j].r);
            j++;
        }
        ans++;

        if (end >= t)
        {
            ok = true;
            break;
        }
        if (end < s)
            break;
        s = end;
        i = j - 1;
    }
    if (ok)
        cout << ans << endl;
    else
        cout << -1 << endl;
    return 0;
}

区间选点

右端点排序,因为每次要选每个区间的右端点,因为越靠后相比较而言

越靠后的点会有更大的机会同时存在于后面的区间

https://www.acwing.com/problem/content/907/

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=2e5+10;
struct node
{
    int l,r;
}record[N];
int cmp(node a,node b)
{
    return a.r<b.r; //按右端点排序
}
int main()
{ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=0;i<n;i++)
{
    cin>>record[i].l>>record[i].r;
}
sort(record,record+n,cmp);
int ans=1;
int end=record[0].r;//每次选区间的右端点
for(int i=1;i<n;i++)   //枚举剩余区间，判断当前区间是否包含选过的点
{
    if(record[i].l>end)
    {
        ans++;  //当前区间不包含选过的点,需要再选一个点,选当前区间的右端点
        end=record[i].r;
    }
}
cout<<ans<<endl;
    return 0;
}

最大不相交区间的数量

https://www.acwing.com/problem/content/description/910/

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=2e5+10;
struct node
{
    int l,r;
}record[N];
int cmp(node a,node b)
{
    return a.r<b.r; //按右断点排序
}
int main()
{ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=0;i<n;i++)
{
    cin>>record[i].l>>record[i].r;
}
sort(record,record+n,cmp);
int ans=1;
int end=record[0].r;//每次选区间的右端点
for(int i=1;i<n;i++)   //枚举剩余区间，判断当前区间是否包含选过的点
{
    if(record[i].l>end)
    {
        ans++;
        end=record[i].r;
    }
}
cout<<ans<<endl;
    return 0;
}

区间分组

https://www.acwing.com/problem/content/908/

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n;
int a[N], k;
int main()
{
    cin >> n;
    while (n--)
    {
        int l, r;
        cin >> l >> r;
        a[k++] = l * 2;     //左端点赋成偶数
        a[k++] = r * 2 + 1; //右端点赋成奇数
    //如果端点可以重合  反过来赋值
    //因为此题端点不可以重合
    //所以说,当前一个区间的右端点和当前区间的左端点相同时,是需要再分一组的
    //所以,把当前区间的左端点变小
    //而对于同一个数,赋成偶数比奇数小1 所以左端点赋成奇数,就处理了重合这种情况
    }
    sort(a, a + k);
    int ans = 0;
    int maxn = 0;
    for (int i = 0; i < k; i++)
    {
        if (a[i] % 2 == 0) //有活动开始,则需要一间教室
        {
            ans++;
        }
        else
            ans--;             //有活动结束,当前活动不需要教室了--
        maxn = max(maxn, ans); //同一时间一个教室不能重叠多个活动,所以取最大值
    }
    cout << maxn << endl;
    return 0;
}

y总做法

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define l first
#define r second
typedef pair<int, int> pii;
priority_queue<int, vector<int>, greater<int>> q;
int n;
pii s[N];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> s[i].l >> s[i].r;
    sort(s, s + n);
    for (int i = 0; i < n; i++)
    {
        pii now = s[i];
        if (q.empty() || q.top() >= now.l) //最小那组的右端点都比大于等于当前区间左端点,肯定会重叠
            q.push(now.r);                 //需要新的一组
        else                               //放在右端点最小的那组
        {
            q.pop();
            q.push(now.r);
        }
    }
    cout << q.size() << endl;
    return 0;
}