植树节浇水问题：求解被浇水次数最多的树苗

植树节浇水问题：求解被浇水次数最多的树苗

植树节快要到了，学校要组织志愿者去给树苗浇水。

有一排树苗，编号依次是 0, 1, 2, ... 。

现有 n 个志愿者去给树苗浇水，第 i 个志愿者选定了一个区间 [start_i, end_i]，表示第 i 个志愿者将 [start_i, end_i] 这一区间内的每一棵树都浇一次水。

如某个志愿者选择的浇水区间为 [4, 9]，表示他将给编号为 4, 5, 6, 7, 8, 9 的树各浇水一次。

当所有的志愿者完成各自所选区间的浇水后，可能有些树苗被不同的志愿者浇水多次，也可能有的树苗一次也没被浇过水。

请你求出浇水最多的树苗被浇了多少次。

输入格式

第 1 行，一个整数 n，表示志愿者的人数。

第 2 行到第 n + 1 行，每行两个整数 start_i, end_i（0 <= start_i <= end_i <= n - 1），表示志愿者 i 选择的浇水区间。

输出格式

输出 1 行，1 个整数，表示浇水最多的树苗被浇水的次数。

输入输出样例

样例一

Input

4
2 4
1 4
6 7

Output

3

样例说明

第 1 名志愿者给编号为 0, 1, 2 的树苗浇水；

第 2 名志愿者给编号 2, 3, 4 的树苗浇水；

第 3 名志愿者给编号 1, 2, 3, 4 的树苗浇水；

第 4 名志愿者给编号 6, 7 的树苗浇水；

编号 0 到 7 的树被浇水的次数依次为： 1, 2, 3, 2, 2, 0, 1, 1 。 所以，被浇水次数最多的是编号为 2 的树，被浇水 3 次

C++ 代码示例

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<pair<int, int>> intervals;

    for (int i = 0; i < n; i++) {
        int start, end;
        cin >> start >> end;
        intervals.push_back(make_pair(start, end));
    }

    vector<int> trees(n, 0);

    for (int i = 0; i < n; i++) {
        for (int j = intervals[i].first; j <= intervals[i].second; j++) {
            trees[j]++;
        }
    }

    int maxWatering = *max_element(trees.begin(), trees.end());

    cout << maxWatering << endl;

    return 0;
}