贪心

1. 区间问题

1.1 区间选点

给定 N个闭区间 ，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;

struct node
{
    int l, r;

    bool operator < (const node &W) const
    {
        return r < W.r;
    }
    
} arr[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> arr[i].l >> arr[i].r;
    
    //按右端点从小到大排序
    sort(arr + 1, arr + 1 + n);
    
    int ans = 0;
    int R = -2e9; //R表示上一连续区间的最右端的点
    for (int i = 1; i <= n; i++)
    {
        if (arr[i].l > R) //如果不能覆盖掉右端点，则点数+1，更新右端点
        {
            ans++;
            R = arr[i].r;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

1.2 最大不相交区间数量

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;

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

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
         cin >> arr[i].l >> arr[i].r;
    
    sort(arr + 1, arr + 1 + n);
    
    int res = 1, R = arr[1].r;
    for (int i = 2; i <= n; i++){
        if (arr[i].l <= R)
            R = min(R, arr[i].r);
        else {
            res++;
            R = arr[i].r;
        }
    }
    
    cout << res << endl;
    
    return 0;
}

1.3 区间分组

给定 N个闭区间 ，要求分成若干组，使得每组内部区间两两之间没有交集，求分成的最小组数。

#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()
{
    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 t = Range[i];
        if (heap.empty() || heap.top() >= t.l) //放不进去则新开一组
            heap.push(t.r);
        else {
            heap.pop();
            heap.push(t.r); //放进去并更新右端点
        }
    }
    
    cout << heap.size() << endl;
    
    return 0;
}

1.4 区间覆盖

给定 N 个闭区间，以及一个线段区间，请你选择尽量少的区间，将指定线段区间完全覆盖。

#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;
    int L, R;
    cin >> L >> R;
    cin >> n;
    
    for (int i = 0; i < n; i++) 
        cin >> Range[i].l >> Range[i].r;
    
    sort(Range, Range + n);
    
    int res = 0;
    bool f = false;
    for (int i = 0; i < n; ){  //依次遍历每个区间
        int j = i, r = -2e9;   //j表示第几个区间
        
        //遍历所有左端点在L的左边的区间，选出右端点最大的
        while (j < n && Range[j].l <= L){
            r = max(r, Range[j].r);
            j++;
        }
        
        if (r < L){  //如果所有右端点都小于L，则无解
            res = -1;
            break;
        }
        
        res++;
        if (r >= R){  //循环出口
            f = true;
            break;
        }
        
        //更新端点和遍历的区间
        L = r;
        i = j; 
    }
    
    if (!f) res = -1;
    cout << res << endl;
    
    return 0;
}

1.5 区间合并

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define PII pair<int, int>
using namespace std;
const int N = 1e5 + 5;

int n;
vector <PII> nums, ans;

void merge(vector<PII> &nums){
    //按左端点排序
    sort(nums.begin(), nums.end());
    
    //l代表区间左端点，r代表区间右端点
    int l = -2e9, r = -2e9;
    for (auto num : nums){
        //如果两区间无法合并
        if (r < num.first){
            if (l != -2e9)
                ans.push_back({l, r});//将新的区间放入ans数组中
                
            l = num.first, r = num.second;//更新区间
        }
        
        //若两区间部分存在交集，小的合并到大的中
        else 
            r = max(r, num.second);
    }
    
    if (l != -2e9)
        ans.push_back({l, r});
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++){
        int l, r;
        cin >> l >> r;
        nums.push_back({l, r});
    }
    
    merge(nums);
    
    cout << ans.size() << endl;
    
    return 0;
}