形式化题意：给定 $m$ 个区间，若删除一个区间后总覆盖面积不变，求出可以被删除的区间数量。

前缀和+差分思想，计算 $1 \sim n$ 中每个位置被覆盖的次数，进而求出被覆盖多次的位置。

最后扫一遍所有区间，若该区间内所有位置都被覆盖多次则计入答案。

c++

#include <bits/stdc++.h>
using namespace std;
/*====================*/
#define ios_close ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define yes puts("Yes")
#define no puts("No")
#define lowbit(x) ((x) & (-x))
#define inf 0x3f3f3f3f
#define endl "\n"
#define PII pair<int, int>
typedef long long LL;
/*====================*/
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
/*====================*/
int n, m;
int L[N], R[N];
int s1[N], s2[N];
int ans;
/*====================*/
void Solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> L[i] >> R[i];
        s1[L[i]]++;
        s1[R[i] + 1]--;
    }
    for (int i = 1; i <= n; i++)
        s1[i] += s1[i - 1];
    for (int i = 1; i <= n; i++)
        s2[i + 1] = s2[i] + (s1[i] > 1);
    for (int i = 1; i <= m; i++)
    {
        if (s2[R[i] + 1] - s2[L[i]] >= R[i] - L[i] + 1)  ans++;
    }
    cout << ans << endl;
    return;
}
/*====================*/
signed main()
{
    ios_close;
    int _ = 1; /* cin >> _; */
    while (_--)
        Solve();
    return 0;
}

java

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 公路长度
        int n = scanner.nextInt();
        // 工人数量
        int m = scanner.nextInt();
        int[][] workers = new int[m][2];
        int[] nums = new int[n + 2];
        for (int i = 0; i < m; i++) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            workers[i][0] = l;
            workers[i][1] = r;
            nums[l] += 1;
            nums[r + 1] -= 1;
        }
        for (int i = 1; i <= n; i++) {
            nums[i] = nums[i-1] + nums[i];
        }
        int ans = 0;
        for (int i = 0; i < m; i++) {
            int l = workers[i][0];
            int r = workers[i][1];
            boolean flag = true;
            for (int j = l; j <= r; j++) {
                if (nums[j] <= 1) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

题目内容

一条长度为$n$的公路上, 米小游站着 $m$名博物工, 其中第$i$位工人会给 $[l_i，r_i]$这一段区间中的每个点都种上一棵树。

但由于每个点最多种一颗, 因此如果某些位工人发现自己要种的地方已经有树, 自己就会跳过这个点不管。

米小游为了节约成本，现在要恰好少雇佣一名工人，但同时他不希望少了此人会影响最终种树的结果，现在请你帮他算算有多少名工人都可以成为恰好少雇佣的这一名呢。

输入描述

第一行输入两个整数 $n, m (1 ≤n≤ 2 × 10^5; 1 ≤ m ≤ 10^5$) 代表公路长度和植树工人数量。

接下来输入$m$行, 每行输入两个正整数$l_i, r_i (1 ≤ l_i ≤ r_i ≤ n)$代表第$i$ 位工人负责种树的区域。

输出描述

在一行上输出一个整数,代表有多少名工人可以被解雇。

5 3
1 4
1 2
3 4

3

说明

三名工人都可以成为被解雇的那一个。 最终的结果是: [1,1,1,1，0] (1表示有物, 0表示没有.) 解雇第一位工人, 神秘结果依然为 [1,1,1,1，0] : 不会影响结果。 解雇第二位工人, 依然不会影响结。 解雇第三位工人, 依然不会影响结果。