$$\color{Red}{区间覆盖=三种语言PII版和贪心版}$$

我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

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

贪心

1.算法细节

• 每次遍历在st左边最长的点，然后把它的右端设置为st，直到能够超越ed，怎么避免双for的O(n ^ 2)?

双指针！
每次从j = i开始遍历，每当遍历到合法点，i的值最后赋值给j-1（因为while循环多加了1），这样保证每找到一个最长可用区间，下次保证从这个区间之后的区间去遍历，节约时间

2.具体代码

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
    static int N = 100010, st, ed, n;
    static int[][] edges = new int[N][2];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        st = Integer.parseInt(s1[0]);
        ed = Integer.parseInt(s1[1]);
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String[] s2 = br.readLine().split(" ");
            edges[i][0] = Integer.parseInt(s2[0]);
            edges[i][1] = Integer.parseInt(s2[1]);
        }
        Arrays.sort(edges, 0, n, Comparator.comparingInt(o -> o[0]));
        boolean flag = false;
        int res = 0;
        for (int i = 0; i < n; i++) {
            int j = i;
            int max_r = -(int) 2e9;
            while(j < n && edges[j][0] <= st){
                max_r = Math.max(max_r, edges[j][1]);
                j ++;
            }
            if (max_r < st) break;
            res ++;
            if (max_r >= ed){
                flag = true;
                break;
            }
            i = j - 1;
            st = max_r;
        }
        if (!flag) res = -1;
        System.out.println(res);
    }
}

python3

st, ed = map(int, input().split())
edge = []
n = int(input())
for i in range(n):
    a, b = map(int, input().split())
    edge.append((a, b))

edge.sort(key = lambda x: x[0])
res = 0
flag = False
for i in range(n):
    j = i
    max_r = -2e9
    while j < n and edge[j][0] <= st:
        max_r = max(max_r, edge[j][1])
        j += 1
    # 若此时最长右端点无法覆盖此时起始点，则为失败
    if max_r < st:  break
    # 能覆盖即答案加1
    res += 1
    # 此时最长右端点超越终点，枚举结束
    if max_r >= ed:
        flag = True
        break
    # 没结束的情况下，区间缩短后继续枚举
    # 因为i每次循环加一，故需要提前减1
    st = max_r
    i = j - 1

if not flag: res = -1
print(res)

C++

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

struct Seg{
    int l, r;
}s[N];

bool cmp(Seg a, Seg b){
    return a.l < b.l;
}

int main()
{
    int st, ed, n;
    scanf("%d%d", &st, &ed);
    scanf("%d", &n);
    for(int i=0; i<n; i++)  scanf("%d%d", &s[i].l, &s[i].r);

    sort(s, s+n, cmp);
    int res = 0;
    bool success = false;
    for(int i=0; i<n; i++)
    {
        int j=i, b = -2e9;
        while(j < n && s[j].l <= st)    b = max(b, s[j].r), j++;

        if(b < st)  break;

        res ++;

        if(b >= ed)
        {
            success = true;
            break;
        }
        st = b;
        i = j - 1;
    }

    if(!success) res = -1;
    printf("%d\n", res);
    return 0;
}