【题目描述】

植树节快要到了，学校要组织志愿者去给树苗浇水。有一排树苗，编号依次是 0,1,2, . . . 。现有 n个志愿者去给树苗浇水，第 i 个志愿者选定了一个区间[ai, bi]，表示第 i个志愿者将 [ai,bi] 这一区间内的每一棵树都浇一次水。如某个志愿者选择的浇水区间为 [4,9] ，表示他将给编号为 4,5,6,7,8,9 的树各浇水一次。当所有的志愿者完成各自所选区间的浇水后，可能有些树苗被不同的志愿者浇水多次，也可能有的树苗一次也没被浇过水。请你求出浇水最多的树苗被浇了多少次？

【输入描述】

第 1 行，一个整数 n，表示志愿者的人数。
第 2 行到第 n + 1 行，每行两个整数 ai, bi（ i= 0,1,2, . . . n− 1） ，表示志愿者 i 选择的浇水区间

【输出描述】

【样例输入1】

4
0 2
2 4
1 4
6 7

【样例输出1】

3

【样例输入2】

4
1000000 1000000
1000000 1000000
0 1000000
1 1000000

【样例输出2】

4

对于所有的数据：n≤ 105；0 ≤ ai≤ bi ≤ 106 。

【参考答案】

#include <bits/stdc++.h>
using namespace std;
int diff[1000002],waterCount[1000001]; //差分数组与浇水数组 
int main() {
    int n;
    cin >> n;
    // 使用差分数组来记录区间加法操作
    for (int i = 0; i < n; ++i) {
        int ai, bi;
        cin >> ai >> bi;
        // 在差分数组中记录区间加法操作
        diff[ai]++;
        diff[bi + 1]--;
    }
    // 计算每棵树的实际浇水次数
    int currentWater = 0;
    int maxWaterCount=-1;
    for (int i = 0; i <= 1000000; ++i) {
        currentWater += diff[i];
        waterCount[i] = currentWater;
        maxWaterCount=max(maxWaterCount,waterCount[i]); // 找出浇水次数最多的树苗
    }
    cout << maxWaterCount <<endl;
    return 0;
}