AcWing 907. 区间覆盖    原题链接    简单

作者： 作者的头像   诠释 ,  2024-04-15 15:46:29 ,  所有人可见 ,  阅读 43

2


区间覆盖简化写法！！！

思路

贪心：将所有区间的左端点按从小到大排序。
1.从前往后枚举每个区间，如果该区间能够覆盖区间起点s，那么选择右端点最大的区间。
2.如果这个最大的右端点能够覆盖终点t，那么就找到一个答案；
3.如果无法覆盖终点t，答案区间数+1，并将区间起点从s改为t，继续遍历区间（返回第1步）。

简化

1.用 pair<int,int> 来表示各个区间，sort的时候会按照第一项first排序，更加简单。
2.只用一个下标 i 来遍历所有区间。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N =100010;
typedef pair<int,int> PII;

int st,ed;
int n;
PII p[N];

int main()
{
    cin >> st >> ed;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        int a,b;
        cin >> a >> b;
        p[i] = {a,b};
    }
    sort(p,p+n);

    int i = 0,res = 0;
    bool flag = false;
    while(i < n)
    {
        int r = -2e9;
        while(i<n && p[i].first <= st)
        {
            r = max(r,p[i].second);
            i++;
        }
        if(r < st)  //找不到能够包含起点st的区间
        {
            res = -1;
            break;
        }
        res++;
        if(r >= ed)
        {
            flag = true;
            break;
        }
        st = r;
    }
    if(flag)
        cout <<res <<endl;
    else cout << -1 <<endl;
    return 0;
}

第一次写题解有错的话大家一起讨论改正~

0 评论

用户头像
20yxzeng   2个月前         踩      回复 
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;


using ll = long long;
using ull = unsigned long long;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;


int main(){ 

    int n, s, t, a, b;
    cin >> s >> t >> n;

    vector<ii> inters;
    for (int i = 0; i < n; i++){
        cin >> a >> b;
        inters.push_back({a, b});
    }

    sort(inters.begin(), inters.end());

    int res = 0, ok = 0;
    for (int i = 0; i < n; i++){
        // 必须注意: 只有 inters[i] 左侧断点小于s 才能进入分组循环
        if(inters[i].first <= s){
            int bg = i, rmost = inters[i].second;
            while (i + 1 < n && inters[i + 1].first <= s){
                rmost = max(rmost, inters[i + 1].second);
                i++;
            }
            res++;
            if ((s = rmost) >= t){
                ok = 1;
                break;
            }
        }
    }

    cout << (ok ? res: -1) << endl;
    return 0;
}

看起来也是分组循环的写法